알고리즘 :: 백준 :: BFS :: 2178 :: 미로탐색

문제

문제접근

문제 이해

• 가장 전형적인 BFS 문제입니다.
  이 문제를 통해 BFS에 익숙해지실 수 있으며, 더 나아가 다익스트라 알고리즘에 대해서 배우게 됩니다.

• 임의의 점으로부터 상, 하, 좌, 우를 검사하면서 진행할 수 있는지, 방문한 적이 없는지를 검사하며 queue에 다음에 이동할 정점을 push()합니다. 그리고 방문표시도 해줍니다.

  Q. 왜 방문표시를 queue에 넣을 때 해주나요?

  A. 중복검사를 막기 위해서입니다. 만일 queue에 넣을 때 방문표시를 하지 않는다면, 인접한 다른 점에서 해당 점을 2회 이상 queue에 넣을 가능성이 있습니다. 따라서 이번 단계(이번 정점)에서 갈 수 있는 모든 점에 대해서는 방문표시를 해둬야만 중복검사를 피할 수 있습니다.

• 이때 목적지에 도착했다면 더 이상 queue 내 원소들을 순회할 필요가 없기 때문에 탐색을 종료합니다.

팁

• 이번 문제를 보면 이동할 수 있는 칸이 1, 이동할 수 없는 칸이 0입니다.
• 이런 경우, 행과 열을 2칸씩 추가해서 만든 뒤 사이드를 갈 수 없는 칸으로 만든다면, 매 loop마다 다음에 갈 좌표가 유효한 좌표인지 확인하지 않아도 됩니다.
• 만일 0과 1이 의미하는 바가 반대라면, 따로 for문으로 초기화 시켜주는 작업이 추가됩니다.
  • 하지만, 0 <= y && y < N && 0 <= x && x < M이라는 4번의 조건문을 최대 N*M번 반복하는 것보다는 초기화를 한 번 수행하는 것이 더 효율적입니다.
• 단, 모든 경우에 대해서 사용하는 방법은 아닙니다. 시점과 종점이 명확하게 있고, 한 번에 이동하는 칸의 개수가 정해져있으며 0과 1의 의미가 이동 가능 여부를 나타낼 때만 가능합니다.
  • 한 번에 이동하는 칸의 개수가 정해지지 않은 경우: 7562번: 나이트의 이동 (acmicpc.net)
  • 0과 1의 의미가 이동 가능 여부가 아닌 경우: 1261번: 알고스팟 (acmicpc.net)

코드

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

int N, M, d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool map[102][102], visited[102][102];

int bfs() {
	queue<tuple<int, int, int>> q;
	q.push({1, 1, 1});
	visited[1][1] = true;
	
	while (!q.empty()) {
		int cy, cx, cost; tie(cy, cx, cost) = q.front();
		if (cy == N && cx == M) return cost;		
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = cy + d[i][0], nx = cx + d[i][1];
			if (!visited[ny][nx] && map[ny][nx]) {
				visited[ny][nx] = true;
				q.push({ny, nx, cost + 1});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	string row;
	for (int y = 1; y <= N; ++y) {
		cin >> row;
		for (int x = 1; x <= M; ++x)
			map[y][x] = (row[x - 1] == '1') ? true : false;
	}
	cout << bfs() << '\n';
}

결과