[백준 2178번 / C++] 미로 탐색

해당 문제를 bfs() 를 활용해서 풀었다. 

 

bfs나 dfs 를 어느정도 활용 할 줄 아시는 분이라면 쉽게 풀수 있을 것이다. 

 

항상 (1,1) 에서 출발하여 해당 지점부터 map 의 1로 저장되어 있는 부분을 지나가면서 

map 의 끝지점까지의 거리를 살펴보면 된다. 

 

첫 시작점부터 map 값이 1인 자리를 visited 배열을 활용해 거리를 갱신해 나간다. 

다음 그림을 보면서 어떤식으로 visited가 갱신되는지 확인해보자 

 

그림은 백준 첫 예제를 토대로 그린 것이다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>
#include <string>
using namespace std;
int map[101][101];
int visited[101][101];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int height;
int width;
queue <pair<int, int>> q;
void bfs() {
	int x, y;
	while (q.size()) {
		tie(y, x) = q.front();
		q.pop(); 
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx < 0 || nx >= width || ny < 0 || ny >= height || !map[ny][nx])continue;
			if (visited[ny][nx])continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny, nx });
		}
	}
	cout << visited[height - 1][width - 1];
	exit(0); 
}

int main() {
	cin >> height >> width; 
	for (int i = 0; i < height; i++) {
		string s; cin >> s; 
		for (int j = 0; j < s.size(); j++) {
			map[i][j] = s[j]-'0';
		}
	}
	visited[0][0] = 1; 
	q.push({ 0,0 }); 
	bfs(); 
	return 0; 
}

 

2178번: 미로 탐색