[백준/C++] 백준 2178번: 미로탐색 (BFS)

 

드디어 BFS에 입문한다. 마구잡이식으로 풀기를 시작했더니 왜 BFS를 쓰는지 아직 모르겠음.. 미로탐색 당연히 DFS로 풀었더니 시간초과가 뜬다. 시간초과가 뜨는 코드는 아래와 같다.

 

#include<iostream>

using namespace std;

int N, M;
int map[101][101];
int dx[] = { 1, 0, 0, -1 };
int dy[] = { 0, 1, -1, 0 };
int ans = 9999;

void dfs(int x, int y, int cnt) {

	if (x == N && y == M) {
		if (cnt < ans) ans = cnt;
	}

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 1 || next_x > N || next_y < 1 || next_y > M) continue;
		if (map[next_x][next_y] == 1) {
			map[next_x][next_y] = 2;
			dfs(next_x, next_y, cnt+1);
			map[next_x][next_y] = 1;
		}

	}

}

int main() {

	
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}

	map[1][1] = 2;
	dfs(1, 1, 1);
	cout << ans;

	
	return 0;
}

 

 

BFS를 쓰는 이유는 마지막에 최단경로만 뽑아내기 때문이라고 한다. 왜 최단경로가 되는거쥐? 찾아보니 아래와 같은 이유 때문이라고 한다.

 

BFS는 자신과 바로 연결되어 있는 노드들을 큐에 넣는다. 그리고 큐는 FIFO에 따라서 가장 먼저 들어온 것들을 가장 먼저 처리한다. 이 두 개가 특성이 결합되서 시작지점으로부터 간선의 수가 작은 곳 부터 먼저 처리한다. 따라서 간선 2개로 연결되어 있는 노드에 도달하는 경우가 간선 1개로 도달하는 경우는 발생하지 않는다.

그래도 아직 잘 모르겠음. 하나 발견하면 깊이 파고드는게 아니라 걍 바로 옆부터 방문하니까 그런지?

여튼 같은 레벨에 있는 애들은 count가 같으니까 전체를 세는 것이 아니라 최단 경로만 딱 세어 준다.

오늘은 여기까지만 생각하고 낼 생각해야징

 

 

BFS 답

 

#include<iostream>
#include<queue>

using namespace std;

int N, M;
int map[101][101] = { 0, };
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };


queue<pair<pair<int,int>,int>> q;
int bfs(int x, int y) {

	q.push(make_pair(make_pair(x, y),1));

	while (!q.empty()) {
		int row = q.front().first.first;
		int col = q.front().first.second;
		int cnt = q.front().second;
		//cout << "(" << row << "," << col << ")" <<  " :" << cnt << endl;

		q.pop();

		if (row == N && col == M)return cnt;

		for (int i = 0; i < 4; i++) {
			int next_x = row + dx[i];
			int next_y = col + dy[i];

			if (next_x < 1 || next_x > N || next_y < 1 || next_y > M) continue;
			if (map[next_x][next_y] == 1) {
				map[next_x][next_y] = 2;
				q.push(make_pair(make_pair(next_x, next_y),cnt+1));
			}
		}
	}


}

int main() {

	
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}


	map[1][1] = 2;
	int ans = bfs(1, 1);

	cout <<  ans;


	
	return 0;
}