[백준 2178번 C++] 미로 탐색

1. 문제 링크

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

2. 문제 설명

도착점(N, M)과 0(이동할 수 없는 칸)과 1(이동할 수 있는 칸)로 이루어진 미로를 입력받은 후,

출발점(1, 1)에서 도착점까지 최단 거리를 출력하는 문제입니다. 따라서 bfs를 사용해야 합니다.

칸을 셀 때에는 시작 위치와 도착 위치도 포함해야 합니다.

 

 

 

 

3. 소스코드

BOJ 2178번 미로 탐색 C++ 풀이입니다.

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

string map[100];
int dis[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	queue<pair<int, int> > q;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	q.push(make_pair(0, 0));
	dis[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 (0 <= nx && nx < N && 0 <= ny && ny < M
			&& dis[nx][ny] == 0 && map[nx][ny] == '1') {
				q.push(make_pair(nx, ny));
				dis[nx][ny] = dis[x][y] + 1;
			}
		}
	}
	cout << dis[N - 1][M - 1];

	return 0;
}

5번 라인 : 미로를 이루고 있는 수들은 붙어서 입력으로 주어지므로 string을 이용하여 한 줄씩 처리하기 위해 string배열을 선언했습니다.

6번 라인 : 방문여부를 체크하고, 거리를 저장할 배열 dis를 이차원 배열로 선언합니다.

7, 8번 라인 : 미로를 그래프로 생각해보면 연결된 정점은 상, 하, 좌, 우 이므로 4방향 좌표를 미리 선언합니다.

15번 라인 : 좌표 형식으로 이루어져 있으므로 queue<pair<int, int>>로 선언합니다.

17, 18번 라인 : 미로를 한줄씩 입력받아 string 배열인 map에 저장합니다.

20번 라인 : 시작점을 make_pair(0, 0)을 이용해 만든 후 q에 push합니다.

21번 라인 : 시작점도 칸을 셀 때 포함해야 하므로 dis[0][0]을 1로 바꿔줍니다.

22번 라인 : q가 비어있지 않는 동안

23번 라인 : x에 현재 방문한 x좌표(q.front().first)를 저장합니다.

24번 라인 : y에 현재 방문한 y좌표(q.front().second)를 저장합니다.

25번 라인 : q.pop()을 이용하여 q에서 빼주고,

26번 라인 : 총 4번(상, 하, 좌, 우) 돌면서

27번 라인 : nx에 다음에 방문할 x좌표(x + dx[i])를 저장하고,

28번 라인 : ny에 다음에 방문할 y좌표(y + dy[i])를 저장합니다.

29번 라인 : nx와 ny가 미로의 범위 안에 있고,

30번 라인 : nx, ny를 방문한 적이 없고 (dis[nx][ny] == 0), 이동할 수 있는 칸(map[nx][ny] == '1')이면,

31번 라인 : make_pair(nx, ny)를 이용해 q에 push한 후,

32번 라인 : dis[nx][ny]는 현재 방문한 좌표의 거리(dis[x][y])에 1을 더하여 저장합니다.

36번 라인 : bfs를 이용했으므로 dis[N - 1][M - 1]에는 (0,0)에서 (N, M)까지의 최단 거리가 저장되어 있고, 이를 출력합니다.