[백준 - 2178] 미로 탐색 (feat. 너비우선탐색) / C++

출처 => https://www.acmicpc.net/problem/2178

 

문제

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

입력

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

출력

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

 

 

사고의 흐름

▶ 너비우선탐색 알고리즘을 이용한 문제이다.

▶ 구하고자 하는 것은 미로를 통과하기 위한 최소한의 칸 수이다. n x m의 칸이 있다면 (0, 0)에서 (n-1, m-1)까지의 칸까지 가는데 필요한 최소한의 칸을 출력해야 하는 것이다. 

 

 

▶ 이 문제에서는 크게 2가지의 포인트가 중요하다! 

 

>> 첫 번째 포인트! 너비우선탐색은 queue를 중심적으로 사용한다!

queue<pair<int, int>>q;
q.push(make_pair(x, y));

▶컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에 깊이우선탐색에서는 스택(Stack)이 사용되지만 너비우선탐색은 큐(Queue)를 사용한다. 문제에서의 지도가 이차원 배열 형태이므로 Queue도 이차원 형태의 <pair<int, int>>큐를 사용한다. 

 

>> 두 번째 포인트! 1이 발견되면 그 점을 중심으로 왼쪽 오른쪽 위 아래를 조사하는 것.

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

▶ 나의 풀이에서는 dx[]와 dy[] 배열을 이용하였다. 주위에 있는 x좌표와 y좌표를 nx와 ny로 설정하고 nx=x+dx[i] ny=y+dy[i]로 선언한다. i가 증가할 때마다 x와 y에 값을 더해준다.

▶ 여기서 중요한 것은 아래의 소스코드처럼 i번째의 숫자는 dx[i]와 dy[i]가 달라야 한다. 만약 0으로 같거나 1,-1로 둘이 같게 된다면 이동하지 않거나 대각선으로 이동하기 때문이다. bfs에서의 움직이는 방향은 수직, 수평 방향이다. 

 

 

>> 세 번째 포인트! 점을 지나면서 지난 칸 수를 누적한다.

check[nx][ny] = check[x][y] + 1;
//check 배열에 누적

cout << check[n - 1][m - 1];
//위의 과정을 이용하면 마지막에 (n-1,m-1) 배열만 출력해주면 됨. 

▶ 0이 벽이고 1이 통로이다. 1을 지나면 칸을 하나 이용하게 되는 것이다. 지날 때마다 check배열에 누적을 한다.

 

소스코드 및 실행결과

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

int map[101][101];//지도
int check[101][101];//방문처리 및 이동한 칸 누적 수
int dx[] = { -1,0,1,0 };//bfs시 x가 움직이는 정도
int dy[] = { 0,1,0,-1 };//bfs시 y가 움직이는 정도
int n, m;//지도의 가로 세로 길이

void bfs(int x, int y) {
//bfs
	queue<pair<int, int>>q;
	//int형이 두개로 이루어진 큐 생성

	q.push(make_pair(x, y));
	//bfs의 매개변수를 q에 push
	//여기서는 (0,0)을 push

	check[x][y] = 1;
	//그 수를 1로 지정(첫번째 칸이므로)

	while (!q.empty()) {

		x = q.front().first;

		y = q.front().second;

		q.pop();
		//그 아래에 있는 것을 front로 옮겨줌

		for (int i = 0; i < 4; i++) {
			//(0,0)을 시작으로 하여
			int nx = x + dx[i];
			int ny = y + dy[i];
			//탐색

			if (0 <= nx &&nx < n && 0 <= ny && ny < m) {
				//만약 bfs의 결과인 (nx,ny)가 지도 안에 있다면
				if (check[nx][ny] == 0 && map[nx][ny] == 1) {
					//방문하적 없고 1이라면(통로라면)
					
					q.push(make_pair(nx, ny));
					//큐에 움직인 결과인 (nx,ny)를 push
					//!q.empty()일 때까지 이 작업을 반복
					//if문이 끝나면 다시 while문으로 들어가서 반복해줌
					//이런식으로 하여 nx==n, ny==m이 될때까지 반복해준다.

					check[nx][ny] = check[x][y] + 1;
					//(nx,ny)를 방문처리해줌, 즉 움직인 칸수를 하나 누적
				}
				else if (check[nx][ny] == 0)
					//만약 통로가 아니라 벽이라면
					check[nx][ny] = -1;
			}
		}
	}
}

void main() {
	cin >> n >> m;
	//지도의 가로 세로 크기 입력

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	//지도의 숫자 입력

	bfs(0, 0);//(0,0)부터 bfs탐색 시작

	cout << check[n - 1][m - 1];
	cout << endl;

}

 

 

의견 및 반성

▶ Queue를 사용해서 비교적 어려운 점도 있었으나 앞에 dx[]와 dy[]를 이용해 이동한다는 점, 재귀함수의 성질을 이용하는 점이 깊이우선탐색 알고리즘과 비슷하여 낯설지는 않았다. 많이 연습해야겠다.