[BFS] BOJ 2178 : 미로 탐색

 

 

 

 

 

백준 알고리즘 강의를 토대로 작성된 문제풀이입니다.
DFS 와 BFS 의 개념에 대해서는 지난 포스트를 봐주세요.
DFS : 2019/05/23 - [프로그래밍/알고리즘] - [알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)
BFS : 2019/05/26 - [프로그래밍/알고리즘] - [알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)
예제 : 2019/07/22 - [프로그래밍/1일1백준] - [Graph] BOJ 1260 : DFS 와 BFS

문제

---

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입력

---

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

---

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이

---

 

이문제 역시

직전 문제와 아주 유사합니다.

2019/08/15 - [백준 문제풀이/GRAPH] - [BFS] BOJ 4963 : 섬의 개수

[BFS] BOJ 4963 : 섬의 개수

 

 

이 문제의 경우는 미로를 탈출하는 최단 경로를 찾는 문제입니다.

시작 위치는 (0,0)

탈출 위치는 (N,M)

즉, 끝에서 끝까지 가는 겁니다.

 

 

최단 거리를 찾는데 다익스트라, 프림 등이 떠오를 수 있습니다.

하지만 이문제는 BFS를 사용하면 쉽게 해결할 수 있습니다.

BFS의 이름은 너비 우선 탐색입니다.

 

따라서 거리순으로 탐색을 한다는 뜻입니다.

가장 처음에 거리가 1인 정점을 탐색

그다음에 거리가 2인 정점을 탐색

.

.

.

 

사진을 보시면 이해가 되시나요?

 

 

따라서 저희는 BFS의 상하좌우를 탐색하는 과정만 유심히 보시면 됩니다!!

 

밑줄 친 코드를 보시면

큐(queue)에 들어있던 좌표값에 1을 더해서

dist[nx][ny] 에 넣어줍니다.

 

여기서 dist[nx][ny] 는 (0,0) 부터 (nx,ny) 까지의 거리를 의미합니다.

약간 dp 문제가 떠오르기도 하네요.

 

이 부분을 제외하고는 특별한 점이 없기 때문에

여기서 설명을 마치도록 하겠습니다.

 

코드

---

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int a[101][101];
int d[101][101];
int dist[101][101]; //거리

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

int main() {

	cin >> n >> m;

	///////미로입력//////
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &a[i][j]);
			d[i][j] = 0;
		}
	}

	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	d[0][0] = 1;
	dist[0][0] = 1;

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

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (a[nx][ny] == 1 && d[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					d[nx][ny] = 1;
					dist[nx][ny] = dist[x][y] + 1;
				}
			}
		}
	}

	cout << dist[n - 1][m - 1] << '\n';
	// 0을 포함한 배열이기 때문에 1을 빼준다.
	return 0;
}