(C++) 백준 2178번 - 미로 탐색

https://www.acmicpc.net/problem/2178

문제

> NxM 크기의 배열로 표현되는 미로가있다.
> 1은 이동가능한 칸, 0은 불가능한 칸을 나타낸다.
> (1,1)에서 출발해 (N,M)의 위치로 이동할 때 지나야하는 최소한의 칸수를 구해라.

접근

이 문제는 경로를 탐색해 최단거리를 구하는 문제이니 BFS를 사용한다. BFS의 대표적인 사용처에 미로탐색이 있다.
BFS로 시작점에서 가능한 경로를 모두 탐색하고 해당 경로로 나아갈 때 1씩 누적해 마지막에 도착했을 때 누적된 값을 출력한다.

문제해결

> BFS를 구현한다. 미로 역할의 miro, 거리를 누적할 dist, 해당 칸이 왔던길인지 검증을 위한 visited, 다음 목적지 탐색을 위해 ,dirR과 dirC를 선언한다.
> dirR과 dirC의 원소는 각각 상하좌우로 이동했을 때의 인덱스의 변화, 좌표의 변화를 뜻한다. R은 row로 행이 위로 이동하면 -1행, 아래로 움직이면 +1행이고 좌우는 상관이 없으므로 0이다. C도 같은 맥락이다.
> 시작점을 받아 큐에 넣고 시작점도 거리에 포함이므로 dist의 초기값을 1로 주고 반복문을 돌린다.
> 들어온 점으로 다음 목적지를 탐색하기위해 복사하고 제거한다. 만약 해당 좌표가 방문했던 곳이면 해당 좌표를 탐색하지않고 넘어간다. 아니라면 방문 마킹을 하고 탐색한다.
> 상하좌우에 대해 연산하며 갈 수 있는 곳이 있나 반복문을 돌린다. 돌려서 나온값이 0보다 작을때(범위 밖), 주어진 미로의 크기보다 클때(범위 밖), 미로상에서의 벽일때(miro가 "0"일때) 해당 방향을 탐색하지않고 넘어간다.
> 가능한 방향이라면 해당 좌표가 미탐색 좌표인지 확인하고 미탐색지역이면 거리를 누적하고 새로운 목적지를 반환해 다음 탐색을 이어간다.
> 구현한 BFS를 통해서 main문에서 vector의 크기, 미로생성 등을 선언해주고 실행한다. 최종점의 dist, 누적된 최종 거리를 출력한다. 인덱스이므로 -1씩 해준다.

코드

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

vector<string> miro;
vector<vector<int>> dist;
vector<vector<bool>> visited;
vector<int>dirR = { -1, 1, 0, 0 };
vector<int>dirC = { 0, 0, -1, 1 };
int N, M;
void BFS(int startR, int startC)
{
	queue<pair<int, int>> q; 
	q.push({ startR, startC });	//시작점을 큐에 넣음
	dist[startR][startC] = 1; //시작점도 거리에 포함

	while (!q.empty())
	{
		int row = q.front().first; //들어온 시작점(도착지)의 row 추출
		int col = q.front().second; //들어온 시작점(도착지)의 col 추출 
		q.pop(); //큐 빼버리기

		if (visited[row][col])
			continue;

		visited[row][col] = true;

		for (int i = 0; i < 4; i++)
		{
			int newR = row + dirR[i];
			int newC = col + dirC[i];

			if ((newR < 0 || newR >= N) || (newC < 0 || newC >= M) || miro[newR][newC] == '0')
				continue;

			if (!visited[newR][newC])
			{
				dist[newR][newC] = dist[row][col] + 1;
				q.push({ newR, newC });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;
	miro.resize(N);
	dist.assign(N, vector<int>(M, 0));
	visited.assign(N, vector<bool>(M, false));
	
	for (int i = 0; i < N; i++) cin >> miro[i];
	BFS(0, 0);

	cout << dist[N - 1][M - 1];
}

후기

BFS를 최근에 공부하게되었는데 마침 BFS를 문제를 만났다. 처음 문제를 봤을땐 멍 했지만 BFS 사용문제인걸 알고서 슥 풀었다. 다음 목적지에 대한 dirR,dirC에 대한 로직은 추가로 공부해서 구현했다. 생각지도 못한 방법이었다.
공부엔 끝이없다.