백준 2178번 - 미로 탐색 (그래프 탐색과 순회, 최단경로와 BFS)

BFS는 여기 적힌 대로, 

큐를 사용해서 인접 노드들을 넓이에 우선하여 탐색하는 기법이다. 

2차원 배열같은 맵에서는 갈 수 있는 곳들이 인접해있을 때, 그 구역 전체를 탐색하고 다음 구역으로 넘어가는 느낌의 수행을 하기도 한다.

 

1. 배경지식 - BFS와 최단경로

이번에 알아볼 BFS의 특징은 바로 최단경로이다. 

BFS는 말 그대로 너비 우선 탐색에 기반하는데, 

너비라고도 할 수 있지만 트리에서 '높이'의 개념처럼 연결된 노드 중 같은 높이, 계층의 노드들을 먼저 모두 탐색한다. 

따라서 원하는 노드에 다다랐다면, 최소한의 계층, 거리를 통과해 도착했다는 것이 보장된다. 

따라서 BFS를 통한 경로가 곧 최단경로인 것이다. 

(단, 가중치가 모두 동일한 경우에 최단경로가 해당된다.  그렇지 않다면 가장 작은 가중치부터 방문하는 알고리즘이 필요할 것이다. )

 

BFS의 seudo code는 다음과 같다. 

1. queue에서 노드를 pop한다.   

node <- Q.pop()

2. node의 인접한 노드들을 모두 큐에 넣는다.

for each v in adjacent(node) : 
	if(Cango(v) && !visited(v))
	    	Q.push(v)

3. 1,2를 큐가 빌 때까지 반복한다. 

while(!Q.isEmpty())
	node <- Q.pop()
	for each v in adjacent(node) : 
		if(Cango(v) && !visited(v))
        	Q.push(v)

 

여기서 2번 과정을 수행하는 동안에는 한 노드에서 연결된 모든 노드를 큐에 담는 과정으로,  모두 시작정점 또는 이전 정점으로부터 같은 거리에 있는 노드들에 큐에 들어간다. 

이 점에 착안해서, distance 배열을 만들고 각 노드까지의 거리를 저장할 수 있다 : 

dis(start) = 0
while(!Q.isEmpty())
	node <- Q.pop()
	for each v in adjacent(node) : 
		if(Cango(v) && !visited(v)):
	        	Q.push(v)
	   	    dis(v) = dis(node) + 1

 

아래와 같은 미로가 있다면, 

distance를 출력하면 다음과 같이 출력된다. 

 

 

2. 코드 구현

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>

int map[101][101];
int visited[101][101];
int dis[101][101] = {0,};
int visit= 1;
int N,M;
#define TRUE 1
#define FALSE 0
using namespace  std;
queue <pair<int,int> >Q;

void BFS()
{
    while(!Q.empty()) {
        int r = Q.front().first;
        int c = Q.front().second;
        Q.pop();
        if (visited[r][c] != FALSE)
            continue;
        visited[r][c] = TRUE;

        if (r + 1 <= N && map[r + 1][c] != 0) {
            Q.push(make_pair(r + 1, c));
            dis[r+1][c] = dis[r][c] + 1;
        }
        if (c + 1 <= M && map[r][c + 1] != 0) {
        Q.push(make_pair(r, c + 1));
            dis[r][c+1] = dis[r][c] + 1;
    }
        if(r-1 >0 && map[r-1][c] != 0) {
            Q.push(make_pair(r - 1, c));
            dis[r-1][c] = dis[r][c] + 1;
        }
        if(c-1 > 0 && map[r][c-1] != 0) {
            Q.push(make_pair(r, c - 1));
            dis[r][c-1] = dis[r][c] + 1;
        }
    }
}
void init()
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            map[i][j] = 0;
            visited[i][j] = 0;
        }
    }
}
void input()
{
    char str[101];
    for(int i=1;i<=N;i++)
    {
        scanf("%s",str);
        for(int j=1;j<=M;j++)
        {
            map[i][j] = *(str+j-1) - '0';
        }
    }
}

void find()
{
    Q.push(make_pair(1,1));
    BFS();
    dis[1][1] = 1;
}
int main() {


    scanf("%d %d", &N, &M);
    init();
    input();
    find();

//    printf("거리 확인용 \n");
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=M;j++)
//            printf("%d ", dis[i][j]);
//        printf("\n");
//    }
    printf("%d", dis[N][M] +1);

}