[BOJ] 백준 2178번 : 미로 탐색(C++)

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

문제풀이

가장 기본적인 bfs문제이다. (1,1)부터 (N,M)까지 지점을 가는데 걸리는 최소 칸 수를 구하는 문제이다.
N, M의 범위가 2~100 이길래 dfs로 풀어도 시간 초과나지 않을 것 같다는 생각을 했는데 문제를 읽어보니 최소 칸 수를 구해야했다. dfs는 최단 경로로 갈 수 없어서 바로 bfs로 접근을 하였다.

입력을 받을 때 숫자간 공백이 없게 입력을 받아야 하므로 고민했는데 char에 받아 int로 바꿔주는 방식으로 구현했다.

queue<pair<int, pair<int, int>>> Q; 를 이용하여 (지나온 칸 수, (y, x)) 표시를 해주었다.
시작 지점도 지난 칸에 해당하므로 지나온 칸 수는 1, 처음 시작점인 (1,1)을 Q에 넣고 visited[1][1] 방문 처리를 해준 후 탐색을 진행하였다.

현재 칸에서 동, 서, 남, 북을 탐색하여

1. row가 1~N, column이 1~M 범위 내에 있음
2. 한번도 방문하지 않음
3. 갈 수 있는 경로(1)

세 가지 조건을 만족하면 visited 처리 후 Q에 삽입하였다.

Q에서 pop한 y의 값이 N, x의 값이 M일때 총 지나온 칸 수를 출력하고 끝날 수 있도록 종료 조건을 설정해주었다.

#include<bits/stdc++.h>
using namespace std;

int board[101][101];
int visited[101][101];
int N, M;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

void input() {

	cin >> N >> M;
	
	char ch;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> ch;
			board[i][j] = ch - '0';
		}
	}
}

void BFS() {
	
	queue<pair<int, pair<int, int>>> Q;
	Q.push({ 1, { 1,1 } });
	visited[1][1] = 1;

	while (!Q.empty()) {
		int dis = Q.front().first;
		int y = Q.front().second.first;
		int x = Q.front().second.second;
		Q.pop();

		if (y == N && x == M) {
			cout << dis;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int curY = y + dy[i];
			int curX = x + dx[i];
			
			if (curY < 1 || curY > N || curX < 1 || curX > M)
				continue;
			if (!visited[curY][curX] && board[curY][curX]) {
				visited[curY][curX] = 1;
				Q.push({ dis + 1 ,{curY,curX} });
			}
		}
	}

}

int main() {

	input();

	BFS();
	
	return 0;
}