BOJ 2178: 미로 탐색

https://www.acmicpc.net/problem/2178

---

알고리즘 분류 | 너비 우선 탐색 (Breadth-First Search, BFS)

풀이 |

BFS 공부를 했는데도 응용 문제가 나오면 헷갈린다.
많은 문제를 풀어봐야겠다.

이건 방문한 지점을 체크하면서 최소의 거리를 체크해야하는 문제이기 때문에 DFS가 아닌 BFS 문제였다.
원래 visited 배열을 썼는데, 갈 수 있는 곳은 1이며 그 길을 지나면 +1을 하면서 기존 배열 값을 +1하며 진행했다.
즉, 거리가 아직 1인 것은 방문한 적이 없다는 뜻이기 때문이다.

처음엔 queue에서 pop할때마다 거리를 +1해주었는데 그렇게 하니 최단경로가 아니라 모든 경로를 방문하게 됐다.
문제에서 원하는 것은 (n, m)에 도착하는 경로이기 때문에,
위의 기존 배열 값에서 +1을 하는 방법을 통해 실제로 (n, m)에 도착하기 까지의 최단 경로를 계산할 수 있었다.

구조체를 만들어 자신 기준 동서남북의 위치를 체크하여 저장된 숫자가 1이라면 방문하는 방식으로 진행했다.

소스 코드 |

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define MAX 101

struct pos {
	int y, x;
};

int m, n;
pos mov[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int num[MAX][MAX];
queue<pos> q;

void BFS(int y, int x) {
	pos start = { y, x };

	q.push(start);

	while (!q.empty()) {
		pos now = q.front();
		q.pop();

		// 아래 위 옆 이동
		for (int i = 0; i < 4; i++) {
			pos newpos = { now.y + mov[i].y, now.x + mov[i].x };

			if (newpos.x < 0 && newpos.x > m - 1 && newpos.y < 0 && newpos.y > n - 1) continue;

			// 방문한 적이 있다면 1이 아닐 것
			if (num[newpos.y][newpos.x] == 1) {
				q.push(newpos);
				num[newpos.y][newpos.x] = num[now.y][now.x] + 1;
			}
		}
	}
}

int main(void) {
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &num[i][j]);

	BFS(0, 0);

	cout <<  num[n-1][m-1] << '\n';

	return 0;
}