[백준알고] [2178]:미로 탐색

하루에 세문제를 풀고 포스팅까지 하다보니..

어느덧 9시간이 훌쩍지났네요..

DFS로는 시간초과가 나는 미로 탐색을 BFS로 풀어봤습니다!

미로 탐색은 시작부터 도착지점 까지 가는 최단 거리 를 구하는 문제입니다!

바로전에 숨바꼭질 문제 포스팅에서 썼던대로! 최단거리는 보통 BFS를 많이 사용합니다.

그럼 포스팅 Start 하겠습니다 ~!!

미로 탐색 성공 풀이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	29159	8972	5518	29.676%

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2≤N, M≤100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 

4 6
101111
101010
101011
111011

예제 출력 

15

예제 입력 2 

4 6
110110
110110
111111
111101

예제 출력 2 

9

N과 M이 주어지고 N행 M열짜리 크기의 맵에서 (0,0) 위치에서 (N-1,M-1) 까지 최단거리로 얼마나 걸리는가를 구하는 문제입니다.

이것을 DFS로 풀어봤을때 시간초과가 났습니다... 왜일까요 ??

BFS같은경우 시작위치부터 너비우선으로 탐색되기 때문에 쭉쭉 뻩어나가서, 도착지점 (N-1, M-1)에 닿으면 그것이 곧 최단거리입니다.

DFS같은경우는 시작위치부터 깊이우선으로 탐색을 하더라도, 결국엔 모든것을 다 탐색한 후에야 도착까지의 최소값을 구해야 하므로 지나봐야 하는 경로가 엄청나게 많습니다.

시간제한이 2초인데 ,, 1초에 십만번 연산되는거보다 훨신 많은 연산이 든다는 뜻이죠..

제가아직 시간복잡도에 대한 개념은 정확히 몰라서.. 무튼 BFS가 훨씬 효과적이고 대충 느낌으로도 DFS로 구현하게되면 이 문제에서 시간초과가 날꺼라는것을 알 수 있습니다.

그럼 제가 어떻게 풀었는지 소스코드로 확인해보겠습니다.

#include<iostream>
#include<queue>
using namespace std;
#define MAX_SIZE 101
int N, M;
char map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int dx[4] = {1, -1, 0, 0};    //동 서 남 북
int dy[4] = {0, 0, -1, 1};    //동 서 남 북
 
int bfs() {
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(0,0),1));    //첫째pair 위치, 둘째pair 움직인거리
    visit[0][0] = 1;
 
    while(!q.empty()) {
        
        int x = q.front().first.second;
        int y = q.front().first.first;
        int z = q.front().second;
        
        q.pop();
 
        if(x == M-1 && y == N-1)
            return z;
 
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= M || ny >= N)
                continue;
            if(visit[ny][nx] == 1)
                continue;
            if(map[ny][nx] != '1')
                continue;
            
            q.push(make_pair(make_pair(ny,nx),z+1));
            visit[ny][nx] = 1;
        }
    }
}
 
int main() {
    
    cin >> N >> M;
    
    for(int i=0; i<N; i++) {
        cin >> map[i];
    }
    cout << bfs();
 
    return 0;
}
 

메인함수는 특별하지 않습니다. 굳이 따지자면, Test Case 의 입력이 정수로 공백띄어쓰기 구분없이 되있는데, int로 받으면 for문을 두번써서 배열의 두번째 인덱스까지 이중 for문을 만들어줘야합니다. 저는 char형 변수를 사용하여, for문을 한번만 사용했습니다..

그 후에 bfs함수를 호출한 결과를 출력했습니다! (함수의 리턴값이 최단거리 값!)

bfs를 보기 전에 어떤 라이브러리들이 참고됬고, 미로를 이동하기 위해서는 어떤 준비가 필요한지 확인해보겠습니다.

먼저, bfs이기 때문에 queue 라이브러리를 참조했습니다.

맵의 크기가 100*100까지 가능하고, 그럼 참조되는 인덱스는 100까지이므로 배열은 101*101로 선언했습니다.

visit 배열은 이동한 경로는 방문체크를 체크하기 위함입니다.

dx, dy 배열은 현재 위치에서 동, 서, 남, 북으로 이동하기 위한 배열입니다. 

dx[0] dy[0] = (1, 0) 은 동쪽, dx[1] dy[1] = (-1, 0) 은 서쪽, dx[2] dy[2] = (-1, 0) 은 남쪽 dx[3] dy[3] (1, 0) = 은 북쪽 입니다....

준비과정을 확인했으니 bfs함수를 살펴보겠습니다.

 
int bfs() {
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(0,0),1));    //첫째pair 위치, 둘째pair 움직인거리
    visit[0][0] = 1;
 
    while(!q.empty()) {
        
        int x = q.front().first.second;
        int y = q.front().first.first;
        int z = q.front().second;
        
        q.pop();
 
        if(x == M-1 && y == N-1)
            return z;
 
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= M || ny >= N)
                continue;
            if(visit[ny][nx] == 1)
                continue;
            if(map[ny][nx] != '1')
                continue;
            
            q.push(make_pair(make_pair(ny,nx),z+1));
            visit[ny][nx] = 1;
        }
    }
}
 
 

pair<T, T> 는 두개의 묶음을 한쌍으로 만드는 문법입니다...

make_pair(값, 값)을 통해 원하는 값을 한쌍으로 만들 수 있습니다.

이 부분은... 구글 검색해서 문법을 공부하시길!

맨 처음 큐에 (0,0)의 위치를 넣고, 처음 이동한 만큼 즉 (1)을 쌍으로 넣어놓습니다.

큐 하나의 공간에, 현재 위치와 얼마나 이동했는가가 pair형태로 저장되있습니다.

while 을 통해 q가 빌때까지 루프를 돌리고, 

끝경로에 도착하면 z를 리턴함으로써 얼마나 이동했는가가 리턴됩니다.

그 아래 for문을 통해 동,서,남,북 위치를 움직일 수 있고,

이동할 위치가 맵을 벗어났을경우, 이미 방문체크한 곳을 가려는 경우, 맵이 0으로 되있는 부분은 continue를 통해 이동을 하지 않습니다.

이동한 후에는 반드시, 이동한 장소를 방문체크 (visit을 1로바꿈) 함으로써 다시 되돌아가는일이 없도록 합니다.

이 코드를 하나하나 말로 풀기가 어려워서.... 이번 포스팅은 설명이 잘 되었는지 모르겠네요 ㅠㅠ

무엇보다, 코드를 보고 테스트케이스를 토대로 맵을 그려가면서 하나하나 따라가보면 이해 될 수 있으리라 믿습니다!!!

그럼 안녕~~~~~~~~~~~~~~~~~~~~~~~