BFS 문제 분석-1(미로탐색)

1. 미로탐색 문제 분석(boj.kr/2178)

이번 문제는 사실 크게 어렵지 않다. 간단한 방법으로 풀 수 있다.

우선, edge는 미로에서 이동할 수 있는 루트를 2차원 배열로 만들어야 한다.

visited를 2차원 배열로 만들어야 한다. 우리가 DFS에서 했던 어떤 문제는 1차원 배열의 형태로 만들었다. 그 이유는, 각 노드에 대한 방문이다. 하지만 여기서는, 각 노드에 대해서 방문하는게 아니라, 배열의 위치를 방문하는 것이다.

우리는 (1,1)에서 최종 목표로 갈 수 있는 최소 칸수를 구해야 한다.  그래서  탐색을 (1.1)에서 시작한다.

화살표의 의미는, 이 바로 다음에 설명하도록 하겠다.

아, 너무 당연하지만 0이면 방문하지않음, 0이 아니면 방문했음을 표현했다.

현재 상태는,  (1,1)에서 방문을 시작한 상태이다.

이제 탐색을 시작해보자.

(1,1)에서 4방탐색을 시작한다. 각각 4방의 위치가 배열의 모서리(?)를 넘는지, 방문하지 않은 위치인지 확인한다.

만약 그렇다면, 현재 위치까지 올 수 있는 경로의 수에서 +1을 해주면 된다.

초록색 화살표를 보면, 현재 위치에서 4방탐색을 한 결과, 바로 밑의 위치에 갈 수 있어서, 현재위치의 경우의 수에서 +1을 해준다.

이 상태에서 쭉쭉해주면 최단경로가 나온다.

다른 testcase를 보도록 하겠다.

현재 미로에서 이동할 수 있는 루트이다.

마찬가지로, (1,1)에서 탐색을 시작한다. 처음 (1,1)에서 4방탐색을 하면, (2,1), (1,2)의 위치를 갈 수 있다. 그러면, 현재 자기자신의 루트까지 올 수 있는 경로의 수에서 +1을 해준다. 그 다음 위치(큐에 남서북동의 우선순위로 넣었다고 가정) (2,1)까지 오는 최단경로에서 +1을 해준다. 하지만, 큐 안에 있는 (1,2)에서 4방탐색을 하면, 이미 탐색이 되었거나, 방문이 완료된 상태이다. 그 다음 위치인, (3,1)에서 다시 4방탐색을 하고, +1을 해준다.

아 그리고 큐 안에 있는 위치에서 빼서 방문체크하면, 다음에 그 방문된 위치의 경로는 항상 최단경로이다. (단, 그 다음위치가 방문되지 않았어야한다.)

코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
 
#define MAX_SIZE 102
 
int edge[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int row[4] = { -1,0,1,0 };
int col[4] = { 0,-1,0,1 };
int N, M;
 
typedef struct _pos {
    int x;
    int y;
}pos;
 
int checkRangeOver(pos p) {
 
    return !(p.x > M + 1 || p.x<1 || p.y>N + 1 || p.y < 1) ? true : false;
}
 
void bfs(int i, int j) {
 
    queue<pos> q;
 
    pos temp, cur;
    temp.x = j; temp.y = i;
 
    q.push(temp);
    visited[temp.y][temp.x] = 1;
 
    while (!q.empty()) {
        temp = q.front();
        q.pop();
 
        if (temp.x == M&&temp.y == N) return;
 
        for (int a = 0; a < 4; ++a) {
            cur.y = row[a] + temp.y;
            cur.x = col[a] + temp.x;
 
            if (checkRangeOver(cur) && !visited[cur.y][cur.x]
                &&edge[cur.y][cur.x]){
                
                q.push(cur);
                visited[cur.y][cur.x] = visited[temp.y][temp.x] + 1;
            }
        }
    }
}
 
int main(void) {
 
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            scanf("%1d", &edge[i][j]);
        }
    }
    
    bfs(1, 1);
 
    printf("%d\n", visited[N][M]);
 
    return 0;
}

나는  여기서 또 scanf를 잘못받아서 틀렸었다..; 함수 다 짜고 이렇게 틀리니까 허무하다.. 우선 입력이 잘 이루워졌는지 확인부터하자..