[백준 2178] 미로 탐색

BFS에서는 이미 방문한 곳은 최소값이 보장되어있음을 이해하는게 중요

visited[newy][newx] = 1 이면 해당 장소는 최소값이 보장되어있다

---

초반에 DFS로 하다 시간초과로 틀린 문제

 

이 문제는 BFS 로 풀어야함

DFS는 첫번째 접근이 최단거리임을 보장해주지 않으므로

목표까지 가는 모든 경우의 수를 종합하여

최소값을 뽑아내야하므로 시간복잡도가 훨씬 큼

 

하지만 BFS는 첫 해가 최단거리임을 보장해줌

따라서 방문을 했으면 최신화하고 아니면 최단거리가 이미 나온 경우이므로 안도는게 맞음

 

왜냐하면 BFS는 각 레벨에 있는 노드들을 순차적으로 큐에 넣고 빼서 검사하는 식이므로

큐에 들어가는 노드들의 레벨은 전 노드 레벨 + 1 로 +1 씩 되어가는 구조이기 때문.

 

그래서 찾고자하는 해의 첫번째 등장이 곧 답이고 최단거리이다

 

https://nulls.co.kr/graph/141

[그래프] 27. BFS로 찾은 경로가 최단 경로인 이유

 

---

#include <iostream>
#include <queue>
#include <bitset>

#define SIZE 101

using namespace std;

int dy[4] = { 0,-1,1,0 };
int dx[4] = { -1,0,0,1 };

int N, M;
bitset<SIZE> map[SIZE];
int visited[SIZE][SIZE] = { 0, };

void solve() {
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	visited[0][0] = 1;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

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

			// 범위 넘거나 갈 수 없거나 이미 방문한 곳이면 skip
			if (newy < 0 || newx < 0 || newy >= N || newx >= M || map[newy][newx]==0 || visited[newy][newx]) continue;

			visited[newy][newx] = visited[y][x] + 1;
			q.push(make_pair(newy, newx));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;

	char ch;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> ch;
			map[i][k] = (ch == '1' ? 1 : 0);
		}
	}

	solve();

	cout << visited[N-1][M-1];

	return 0;
}