백준 문제풀이 : (2178) 미로 탐색 - C/C++ : BFS, DFS로 풀기

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

2178번: 미로 탐색

 

시간 제한	메모리 제한	난이도	알고리즘 분류
1초	192 MB	Silver 1	그래프, BFS

 

 

문제 

 

 

풀이

그래프 경로 탐색에서 최단 거리를 구하는 문제이다. 목표 지점까지 도달하는 경우의 수를 구하는 문제라면 한 라인을 끝까지 검사하는 DFS가 적합하겠지만, 해당 문제는 최단 거리를 요구하고 있으므로 모든 가능 경로를 한 노드씩 번갈아가며 점검해나가는 BFS가 시간복잡도 측면에서 훨씬 적합하다.

 

게다가 시간 제한을 1초로 제한하고 있기 때문에 DFS를 사용할 경우 시간 초과가 발생한다. 

 

하지만 DFS와 BFS를 공부 중이기 때문에 두 가지 방법을 모두 사용해 문제를 해결해 보았다. 

 

 

(1) DFS로 풀어보기

DFS 설계 시 가장 중요한 사항은 재귀를 탈출 할 수 있는 제한 조건을 찾아내는 것이다. (N, M) 위치까지 도달하는 최단 경로를 구하기 위함이니 검사 좌표가 (N, M)에 도달했을 때 여태까지 지나온 칸 수를 저장하고 탈출하도록 코딩을 해보자.

 

단, (N,M) 까지 도달하는 가지수는 여러개일 수 있으므로 최소값 검사를 마친 후 저장해줘야 한다.

 

void dfs(int x, int y, int n, int m, int count) {
//x, y : 검사 중인 좌표
//n, m : 목표 좌표
//count : 검사한 칸 수
//check[][] : 검사한 칸 표시 (검사 중인 경로에서 검사한 칸을 다시 지나지 않기 위함)
//map[][] : TC로 주어진 맵 테이블

    if (x==n && y==m) { 
        if (minn>count) minn=count;
        return ;
    };
    
    check[x][y]=1; //검사한 칸은 다시 검사하지 않으므로 check테이블에 1을 저장.
    
    if (x<n) { //x,y 좌표는 맵 테이블의 범위를 벗어나서는 안된다.
    	if (!check[x+1][y] && map[x+1][y]) {
        //다음 검사 칸은 이미 검사한 칸이 아니어야 하며, 맵 테이블 값이 1이어야 한다.
        	dfs(x+1, y, n, m, count+1); 
        }
    }
    
    if (y<m) { if (!check[x][y+1] && map[x][y+1]) dfs(x, y+1, n, m, count+1); }
    
    if (x>1) { if (!check[x-1][y] && map[x-1][y]) dfs(x-1, y, n, m, count+1); }
    if (y>1) { if (!check[x][y-1] && map[x][y-1]) dfs(x, y-1, n, m, count+1); }
    
    check[x][y]=0; 
    //해당 경로 검사 후에는 다른 경로에서 해당 칸을 방문할 가능성이 있으므로,
    //다시 check테이블 값을 0으로 초기화해준다.
}

 

문제에서의 시간제한 때문에 모든 TC에서 정답인지는 확인할 수 없었지만 예제로 주어진 TC에서는 전부 정답이었다.

 

 

(2) BFS로 풀어보기

BFS는 재귀함수가 아닌 que 구조를 사용한다. c++ STL에서 제공하고 있는 deque 라이브러리를 이용해 편하게 코드를 구현해보자. (1, 1) 좌표를 시작으로, 그 근처에 검사 가능한 칸들을 deque에 저장해나가며 경로를 검사한다. 해당 방식은 이전에 '지뢰찾기'를 구현했던 방식과 유사하다.

 

또한, 최소 경로의 검사 칸 수를 출력해야하므로 각 칸 까지의 거리를 저장하는 테이블이 하나 더 필요하지만, 해당 코드에서는 map 테이블 배열에 거리값을 바로 저장해줬다. (dfs와 달리 bfs는 모든 경로의 노드를 한번씩 건드리며 전진하기 때문에 중복 방문하게되는 노드가 없다. dfs처럼 틀린 경로에서 되돌아가는 구조가 아니기 때문에 check테이블 초기화를 신경 써줄 필요가 없다.)

 

void bfs(int x, int y, int n, int m) {
//x, y : 검사 중인 좌표
//n, m : 목표 좌표
//check[][] : 검사한 칸 표시 (검사 중인 경로에서 검사한 칸을 다시 지나지 않기 위함)
//map[][] : 
// - TC로 주어진 맵 테이블
// - 검사 후에는 해당 칸 까지 지나온 칸 수를 저장

    deque<int*> dq;
    dq.push_back(new int[]{x, y}); //첫번째 칸인 1,1 을 deque에 저장한다.
    int movex[] = {-1, 0, +1, 0};
    int movey[] = {0, 1, 0, -1};
    //이동가능한 칸은 상, 하, 좌, 우 네 가지이므로 각 방향에 맞게 이동값을 생성한다.
    
    while(dq.size()>0) {
        //dq가 텅 빌때까지 반복. 마지막으로 꺼내는 노드는 가장 멀리 있는 (N,M)이 된다.
        int* pop = dq.front();
        dq.pop_front();
        x=pop[0];
        y=pop[1];
        
        for (int k=0 ; k<4 ; k++) {
            int px=x+movex[k]; //deque에 넣을 수 있는 노드 좌표를 검색 및 생성
            int py=y+movey[k];
            //deque에 넣을(이후 꺼내서 주변 노드를 검색할) 노드가 유효성에 부합하는지 검사
            if (px>=1 && py>=1 && px<=n && py<=m) {
            //큐에 넣을 노드는 맵 테이블 크기 안에 있어야 한다.
                if (map[px][py] && !check[px][py]) {
                //큐에 넣을 노드는 미방문 노드여야 하고, 맵 테이블 값이 1이어야 한다. 
                    check[px][py]=1; //큐에 넣을 것이니 체크
                    map[px][py] = map[x][y]+1; 
                    //해당 노드까지의 칸 수는 이전 노드까지의 칸 수 +1
                    dq.push_back(new int[]{px, py}); //검색 큐에 저장
                }
            }
        }
    }
}

 

 

코드 구현 (전체)

#include <iostream>
#include <cstring>
#include <deque>

using namespace std;
int map[101][101]; //시작 칸 좌표가 1,1 이기 때문에 맵 크기도 1씩 더해줬다.
int check[101][101];

int minn=1000; //첫 최소값 비교를 위해 큰 값으로 더미데이터 입력

//dfs
void dfs(int x, int y, int n, int m, int count) {

    if (x==n && y==m) {
        if (minn>count) minn=count;
        return ;
    };
    
    check[x][y]=1;
    
    if (x<n) { if (!check[x+1][y] && map[x+1][y]) dfs(x+1, y, n, m, count+1); }
    if (y<m) { if (!check[x][y+1] && map[x][y+1]) dfs(x, y+1, n, m, count+1); }
    
    if (x>1) { if (!check[x-1][y] && map[x-1][y]) dfs(x-1, y, n, m, count+1); }
    if (y>1) { if (!check[x][y-1] && map[x][y-1]) dfs(x, y-1, n, m, count+1); }
    
    check[x][y]=0;
}

//bfs
void bfs(int x, int y, int n, int m) {
    deque<int*> dq;
    dq.push_back(new int[]{x, y});
    int movex[] = {-1, 0, +1, 0};
    int movey[] = {0, 1, 0, -1};
    
    while(dq.size()>0) {
        
        int* pop = dq.front();
        dq.pop_front();
        x=pop[0];
        y=pop[1];
        
        for (int k=0 ; k<4 ; k++) {
            int px=x+movex[k];
            int py=y+movey[k];
            
            if (px>=1 && py>=1 && px<=n && py<=m) {
                if (map[px][py] && !check[px][py]) {
                    check[px][py]=1;
                    map[px][py] = map[x][y]+1;
                    dq.push_back(new int[]{px, py});
                }
            }
        }
    }
}


int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    
    for (int n=1 ; n<=N ; n++) {
        for (int m=1 ; m<=M ; m++) {
            scanf("%1d", &map[n][m]);
            //TC에서 숫자가 붙어있을 경우, %와 d사이에 숫자(n)을 넣으면 n개씩 입력받음.
        }
    }
    
    dfs(1, 1, N, M, 1);
    printf("%d", minn);
    
    //bfs(1, 1, N, M);
    //printf("%d", map[N][M]);
}

 

 

END