[백준 2178] 미로 탐색

https://acmicpc.net/problem/2178

 

---

해설

이번 문제인 미로 찾기는 전에 소개한 백준 7562 나이트의 이동( 참고 : https://far-simple.tistory.com/10 ) 문제와 동일해서 설명은 생략하겠다.

다만, di 배열과 dj 배열을 잡을 때만 조심해주면 된다.

7562는 색칠 된 부분이 매우 많고 범위도 컸지만, 이번에는 아래 소스코드와 같이 위, 오른쪽, 아래, 왼쪽만 di, dj 배열로 잡아주면 끝난다.

 

int di[4] = {-1,0,1,0};
int dj[4] = {0,1,0,-1};

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <queue>

int di[4] = {-1,0,1,0};
int dj[4] = {0,1,0,-1};
int arr[101][101];
bool visited[101][101];
using namespace std;
int main(){
	int n, m; cin >> n >> m;
	for(int i=0; i<n; i++){
		string a; cin >> a;
		for(int j=0; j<a.size(); j++)
			arr[i][j] = a[j] - '0';
	}
	using p = pair<int, pair<int, int > >;
	queue<p> q;
	q.push({0,{0,1}});
	visited[0][0] = true;
	while(!q.empty()){
		p f = q.front();
		if(f.first == m-1 && f.second.first == n-1){
			cout << f.second.second << '\n';
			break;
		}
		q.pop();
		for(int i=0; i<4; i++){
			int xx = f.first + dj[i];
			int yy = f.second.first + di[i];
			if(xx>=0 && yy>=0 && xx<m && yy<n)
				if(!visited[yy][xx] && arr[yy][xx] == 1){
					visited[yy][xx] = true;
					q.push({xx,{yy,f.second.second+1}});
				}
		}
	}
}