[백준 알고리즘] 2178번: 미로탐색
May 05, 2020
https://www.acmicpc.net/problem/2178
문제
문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
풀이
BFS를 통해서 해결할 수 있었다. 문제에서 시작점을 (1, 1) 로 정해두어서 배열을 넘어서는 예외처리를 따로 해줄 필요가 없었다. 배열을 어차피 0번째부터 만들고 false 로 초기화 되어 있을거니까 그냥 true인지 false인지 확인해주기만 하면 위치를 벗어났는지 확인이 된다. 이번 문제에서는 다른 bfs 문제와는 조금 다르게 목적지에 도달하기까지 만들었던 트리의 레벨을 계속 기록해주어야 한다. 한번에 큐에 여러 값을 넣기 때문에 push의 갯수로는 레벨을 확인할 수 없다. 한가지 힌트를 얻을 수 있는 점은, 각 레벨의 마다 돌아야 하는 노드의 갯수는 그 상위 레벨에서 이미 결정이된다. 왜냐하면 bfs는 인접노드를 모두 순회해야하기 때문에 한 레벨의 순회가 끝난 시점에서는 이미 다음 레벨의 인접 노드들의 구성이 모두 큐에 들어가 있는 상태일 것이기 때문이다.
따라서 한 레벨이 시작할 때 큐의 크기를 저장해두고 해당 크기만큼 순회를 마친다면 한 레벨에 대한 탐색이 끝났다고 해도 될 것이다. 그리고 목적지 지점을 만났을 때는 그냥 바로 bfs 함수를 빠져나와서 해당 지점에서 한칸 더 이동한 값을 최종 결과로 출력해주면 된다.
코드
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
bool visited [101][101];
bool map[101][101];
int N, M;
int cnt = 0;
vector<vector<int>> adj (101);
void bfs(int y, int x){
queue<pair<int, int>> q;
int xdir [] = {1, -1, 0, 0};
int ydir [] = {0, 0, 1, -1};
q.push(make_pair(y, x));
visited[y][x] = true;
while(!q.empty()){
int size = q.size();
for (int k = 0 ; k < size ; k++){
pair<int, int> node = q.front();
q.pop();
if ((node.first == N) && node.second == M) return;
for (int i = 0 ; i < 4 ; i++){
int nextY = node.first + ydir[i];
int nextX = node.second + xdir[i];
if (map[nextY][nextX] == true && visited[nextY][nextX] == false){
visited[nextY][nextX] = true;
q.push(make_pair(nextY, nextX));
}
}
}
cnt++;
}
}
int main (){
scanf ("%d %d", &N, &M);
for (int i = 1 ; i <= N ; i++){
for (int j = 1 ; j <= M ; j++){
scanf("%1d", &map[i][j]);
}
}
bfs(1, 1);
printf("%d", cnt+1);
}
