[백준] 2178. 미로 탐색

문제

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



풀이

DFS로 풀게 되면 모든 경우의 수를 전부 구하고 최소값을 구하기 때문에 시간초과가 생기지만, BFS로 풀면 너비 순, 즉 인접해있는 것부터 탐색하면서 (N, M)에 도달하는 순간 멈춰버리므로 BFS가 적절하다고 볼 수 있다. 즉 DFS는 (1, 1)부터 (N, M)까지 가는 경로의 경우의 수를 구하는 것이라면, BFS는 (1, 1)부터 (N, M)가지 가는 경로의 최단거리를 구하는 것이다.
그래서 최단거리 문제는 대부분 BFS로 풀게 된다.

문제의 풀이는 3가지 조건을 고려하면서, 현재 위치에 인접해 있는 경로를 탐색한다.

1. 다음 경로가 x > 0, y > 0인가?
2. 다음 경로가 x <= M, y <= N 인가?
3. 다음 경로에 저장되어 있는 값이 1인가?

x, y가 0보다 작거나 같으면 미로에서 벗어나게 된다. M, N보다 큰 경우도 마찬가지이다. 즉 미로 안에 있는지 여부를 탐색하는 것이다.
또한 문제에서 1일 때만 지나갈 수 있다고 명시되어 있는데, 경로를 탐색하면서 지나갈 수 있는 경로면 저장되어 있는 값에 +1을 해주어서 다른 경로의 탐색 차례에 이미 탐색을 마친 경로를 다시 탐색할 일이 없게 해준다.

   [1][2][3][4][5][6]
[1] 1  1  1  1  1  0
[2] 1  0  1  0  0  0
[3] 1  0  1  0  0  0
[4] 1  1  1  0  0  0
[5] 1  0  1  0  0  0
[6] 1  0  1  1  1  1

위와 같은 경우 (1, 2)로 가는 경로가 끝나고 다른 경로들은 전부 다 탐색해 볼 필요도 없이 중간에 끊기게 된다. 이로써 연산을 최소로 줄일 수 있게 된다.



소스코드

//
//  SearchingMaze.cpp
//  test
//
//  Created by 신기열 on 01/06/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <queue>
#include <iostream>

using namespace std;

int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
int maze[101][101];
queue <int> q;
int N, M;

void BFS(){
    
    q.push(make_pair(1, 1));
    
    while(!q.empty()){
        int curr_x = q.front().second, curr_y = q.front().first;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            
            int next_x = curr_x + dir[i][1], next_y = curr_y + dir[i][0];
            
            //maze[next_y][next_x] = 1 일 때만 지나간다 -> 간선의 방향이 한방향인 너비 우선 탐색
            //예제 입력 2에서 보면 처음에 오른쪽과 밑쪽으로 이동할 수 있는데, 이 때 둘 중 먼저 연산 한 것에 의해 (이 경우 밑쪽이 연산이 먼저됨)
            //인접한 값들도 2로 변경되면서 다음 노드가 탐색을 하지 못하게 되므로 억지로 멀리 돌아가서 계산하는 경우는 고려할 필요가 없어짐
            //그냥 순서대로 연산하다보면 결국 최소 거리가 나오게 됨
            if(next_x > 0 && next_y > 0 && next_x <= M && next_y <= N && maze[next_y][next_x] == 1){
                q.push(make_pair(next_y, next_x));
                maze[next_y][next_x] = maze[curr_y][curr_x] + 1;
            }
        }
    }
    
}

int main(){
    
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            //어떤 정수가 주어졌을 때, 한자리씩 띄어서 저장. 즉 치는 즉시 저장이 된다. (공백 빼고)
            scanf("%1d", &maze[i][j]);
        }
    }
    
    BFS();
    cout << maze[N][M];
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/DFSorBFS/SearchingMaze.cpp