알고리즘(C++) / 백준 2178 : 미로탐색

2178

boj.kr/2178

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

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

 

코드

//2178 미로탐색
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

char miro[101][101];
bool visited[101][101] = { false, };
int num[101][101] = { 0, };
int N, M;
int dir_x[4] = { 1, 0, -1, 0 }, dir_y[4] = { 0, 1, 0, -1 };

void BFS(int x, int y) {
	visited[x][y] = true;
	num[x][y] ++;

	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	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 + dir_x[i];
			int ny = y + dir_y[i];
			if (nx < 0 || ny <0 || nx >= N || ny >= M)
				continue;
			if (visited[nx][ny] == false && miro[nx][ny] == '1') {
				visited[nx][ny] = true;
				q.push(make_pair(nx, ny));
				num[nx][ny] = num[x][y] + 1;

			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> miro[i][j];
		}
	}

	BFS(0, 0);

	cout << num[N-1][M-1] << endl;


	return 0;
}

 

설명

DFS는 최단경로라는 보장이 없고, BFS는 최단경로를 찾을 수 있다. 그래서 BFS를 이용하여 구현한다.

 

mrio 배열에 입력을 받는다.

BFS함수를 0,0부터 시작한다. 방문한 칸들은 값을 true로 변경해준다.

queue는 pair로 x,y의 값을 저장한다. q에 가장 처음을 push해준다. 

노드는 방향은 시계방향대로 우측, 아래, 왼측, 위 순으로 방문하게 된다. 

 

num배열은 최단경로를 구해준다. 처음 위치에서 몇 칸을 지나야 최단경로로 갈 수 있는지 알 수 있다. BFS는 넓이 우선 탐색이므로 최단 경로를 구할 수 있다. 

 

결과

 

고찰

이번 문제에서는 자료형을 잘못 받아와서 틀렸다. 

배열을 입력받을 때 숫자들을 입력받아서 당연히 int형으로 선언하였지만 int형으로는 범위를 만족시키지 못한다.

그래서 char로 문자형으로 입력받을 수 있었다. 

범위를 잘 생각해서 입력받아야한다.

 

난이도

●◐○○○