백준 온라인 저지 | 2178번 미로 탐색 | C++

백준 온라인 저지 | 2178번 미로 탐색 | C++

2178번: 미로 탐색

 

1. 문제 접근

■ 1.1 4방위 너비 우선 탐색

 0 혹은 1로 이루어진 미로에서 한 칸에서 다른 칸으로 이동할 때 서로 인접한 칸으로 이동할 수 있다고 되어 있다. 이것으로 미루어 보아 2차원 평면에서 한 정점에 인접한 사방위 너비 우선 탐색을 수행하는 것이 적절해 보인다.

 

■ 1.2 최단 거리

 시작 위치 (1, 1)에서 출발하여 도착 위치 (N, M)으로 이동할 때 지나야 하는 최소 칸 수를 구한다는 말은 정점 (0, 0)에서 정점 (N-1, M-1)의 최단 거리를 구한다는 말과 동치이다. 시작 위치 (1, 1)에서 도착 위치 (N, M)까지 항상 이동할 수 있는 입력이 주어지므로 정점 (0, 0)에서 너비 우선 탐색을 수행한 다음, 정점 (N-1, M-1)와의 최단 거리를 구하면 된다. 이때 한 정점에서 다른 정점까지의 최단 거리를 저장할 2차원 벡터 dist를 사용한다.

 

2. 문제 풀이

1. 미로 정보를 저장할 2차원 벡터 adj와 정점을 방문했는지와 시작 위치와의 최단 거리를 저장할 2차원 벡터 dist를 선언한다. adj와 dist의 크기는 N×M으로 설정하고 주어진 미로 정보로 adj를 초기화한다.
2. 정점 (0, 0)을 큐에 넣고 dist[0][0]을 0으로 초기화한 다음, 너비 우선 탐색을 수행한다.
   • 큐에 정점이 있으면 큐에서 정점을 꺼낸다.
   • 이 정점으로부터 새로운 사방위 정점을 만든다. 새로운 정점이 배열의 범위를 벗어나거나, 이미 거리가 측정된 정점이거나, adj 정보가 0인 경우 다음 정점으로 넘어간다.
   • 그 외 새로운 정점은 이전 정점의 dist에 1만큼 더하고 큐에 넣는다. 그리고 큐가 빌 때까지 위의 과정을 반복한다.
3. 시작 위치 (1, 1)부터 도착 위치 (N, M)의 최단 거리인 dist[N-1][M-1]에 1을 더해 출력한다.

 

3. 문제 해결

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

void makeGraph();
void bfs(int x, int y);

// 인접 행렬로 미로를 표현합니다.
vector<vector<int>> adj;
// 시작 정점 (0, 0)과의 거리를 저장합니다.
vector<vector<int>> dist;
// 너비 우선 탐색에 사용할 큐입니다.
queue<pair<int, int>> q;

int N, M;
// 인접한 상하좌우 정점의 좌표를 만드는 데 사용합니다.
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	makeGraph();
	bfs(0, 0);
	cout << dist[N - 1][M - 1] + 1 << '\n';
	return 0;
}

// 주어진 미로 데이터로 인접 행렬 그래프를 만듭니다.
void makeGraph() {
	cin >> N >> M;
	// 벡터 adj, dist의 크기를 N * M으로 설정합니다.
	adj = vector<vector<int>>(N, vector<int>(M, 0));
	dist = vector<vector<int>>(N, vector<int>(M, -1));

	// 주어진 미로 정보로 adj를 초기화합니다.
	for (int i = 0; i < N; ++i) {
		string maze;
		cin >> maze;
		// ASCII 코드의 문자 '0'을 빼서 0 혹은 1로 정점을 초기화합니다.
		for (int j = 0; j < M; ++j) {
			adj[i][j] = maze[j] - '0';
		}
	}
}

// 너비 우선 탐색 알고리즘을 구현합니다.
void bfs(int x, int y) {
	// 너비 우선 탐색을 시작할 정점을 큐에 집어넣습니다.
	dist[x][y] = 0;
	q.push({ x, y });

	while (!q.empty()) {
		// 큐에서 정점을 꺼냅니다.
		pair<int, int> pos = q.front();
		q.pop();

		// 사방위 정점을 확인합니다.
		for (int i = 0; i < 4; ++i) {
			int nx = pos.first + dx[i];
			int ny = pos.second + dy[i];
			// 새 정점의 좌표가 배열의 범위를 벗어나는 경우 다음 정점으로 건너뜁니다.
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
				continue;
			}
			// 새 정점의 정보가 0이거나 이미 방문한 경우 다음 정점으로 건너뜁니다.
			if (!adj[nx][ny] || dist[nx][ny] > -1) {
				continue;
			}
			// 새 정점의 최단 거리는 이전 정점의 최단 거리에 1만큼 더한 것입니다.
			dist[nx][ny] = dist[pos.first][pos.second] + 1;
 			// 그외 정점은 큐에 집어넣습니다.
			q.push({ nx, ny });
		}
	}
}

 

2178번 미로 탐색 성공

 

4. 문제 고찰

■ 4.1 붙어서 주어지는 입력

 문제에서 주어지는 0 혹은 1의 데이터가 공백으로 구분되어 있다면 이중 for문과 cin 함수를 사용하여 벡터 adj를 초기화할 수 있다. 하지만 0 혹은 1의 데이터가 공백으로 구분되지 않고 연속된 수로 주어진다면 cin만으로는 초기화할 수 없다. 대신에 문자열로 데이터를 받고 각 문자마다 문자 '0'을 빼주어 adj를 초기화해야 한다. 문자 '0'의 ASCII 코드는 48이고 문자 '1'의 ASCII 코드는 49이므로 각 문자에 문자 '0'을 빼면 정수 0(48 - 48 = 0)과 정수 1(49 - 48 = 1)을 구할 수 있다.

// 공백으로 구분된 0과 1 데이터는 다음과 같이 초기화합니다.
for (int i = 0; i < N; ++i) {
	for (int j = 0; j < M; ++j) {
		cin >> adj[i][j];
	}
}

// 공백으로 구분되지 않은 연속된 0과 1 데이터는 다음과 같이 초기화합니다.
for (int i = 0; i < N; ++i) {
	string data;
	cin >> data;
	// 문자열 data에서 ASCII 코드의 문자 '0'을 각각 빼주어 adj를 초기화합니다.
	for (int j = 0; j < M; ++j) {
		adj[i][j] = string[j] - '0';
	}
}

 

■ 4.2 최단 거리 혹은 최소 이동 횟수

 다른 너비 우선 탐색과 달리 최단 거리를 구하는 BFS 문제는 vector<vector<bool>> visited 대신 vector<vector<int>> dist를 사용한다. visited는 정점의 방문 여부를 true와 false로 나타냈지만, dist는 정점을 방문하지 않았으면 -1, 정점을 방문했다면 시작 위치와의 최단 거리인 양수 k로 나타낼 수 있기 때문이다.

 한편, 어떤 한 정점의 최단 거리는 이전 정점의 최단 거리에 1만큼 더한 것이다. 사방위 정점은 중앙 정점으로부터 한 칸씩 떨어져 있기 때문이다. 이러한 속성을 사용하면 이전 정점의 최단 거리인 dist[pos.first][pos.second]에 1만큼 더해 새로운 정점의 최단 거리인 dist[nx][ny]를 구할 수 있다.