[백준/BOJ] 2178번: 미로 탐색 ( 너비 우선 탐색, BFS 활용법 ) - C++ 문제 풀이

 

문제 설명

 

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

 

풀이

이 문제는 (1,1)부터 시작해서 (N, M) 위치에 도달하는데 필요한 최소 이동 거리를 구하는 문제입니다.

 

이 문제에서는 "2667번 단지 번호 붙이기" 문제에서처럼 좌표를 이용해서 문제를 푸는 대신

입력 데이터로부터 그래프를 구성해서 해결하는 방식을 사용했습니다.

 

"2667번 단지 번호 붙이기" 문제는 여기에 링크를 하겠습니다.

[백준/BOJ] 2667번: 단지 번호 붙이기 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

 

먼저, 문제가 입력하는 데이터를 가지고 그래프(graph)를 구성하겠습니다.

#define SIZE 100
typedef short MTYPE;

// 1이 있는 위치를 표시하고, 방문한 노드를 표시하기 위한 변수
bool visited[SIZE*SIZE];

// 정점에 연결되어 있는 정점들의 vector 배열
vector<MTYPE> graph[SIZE*SIZE];	

// (i1, j1)와 (i2, j2) 간의 edge를 저장
void AddEdge( MTYPE i1, MTYPE j1, MTYPE i2, MTYPE j2){
    MTYPE v1 = i1*M + j1;
    MTYPE v2 = i2*M + j2;

    graph[v1].push_back(v2);
    graph[v2].push_back(v1);
}

// (i,j) 위치에 1이 있는지 확인
inline bool& IsExist(MTYPE i, MTYPE j){
    return visited[i*M+j];
}


scanf("%d %d", &N, &M);	// 미로의 크기

char str[SIZE+1] = {'\0'};
bool bExist;
for( int i = 0; i < N; i++){

    scanf( "%s", str);	// 미로 데이터 입력

    for( int j = 0; j < M; j++){
        bExist = false;
        if (str[j] == '1')	
            bExist = true;

        IsExist(i, j) = bExist;	// 숫자 1이 있는 위치 표시
        
        if ( bExist){

    	    // 현재의 왼쪽에 1이 있으면 간선 구성
            if ( j > 0 && IsExist(i, j-1)){
                AddEdge(i, j-1, i, j);
            }
            
            // 현재의 위쪽에 1이 있으면 간성 구성
            if ( i > 0 && IsExist(i-1, j)){
                AddEdge(i-1, j, i, j);
            }
        }
    }
}

위의 코드는 숫자 1이 있는 위치를 하나의 정점(vertex)으로 보고, 숫자 1과  다른 숫자 1이 있는 위치가 인접하면, 간선(edge)을 저장하여 그래프를 구성하는 코드입니다.

(i, j) 위치의 정점은 숫자 i*m + j으로 표시했습니다. ( 정점은 0부터 N*M-1까지의 숫자로 표시 )

그리고, 간선은 방향성이 없으므로 왼쪽과 위쪽 간선만 차례차례 저장하면 모든 간선을 저장할 수 있습니다.

 

이제, 그래프를 구성했으므로 이를 사용하여 너비 우선 탐색( BFS )으로 최단 이동 거리를 찾을 수 있습니다.

 

너비 우선 탐색에 관한 내용은 여기에서 볼 수 있습니다.

[백준/BOJ] 24445번: 너비 우선 탐색 2 ( BFS, Breath-First Search ) - C++ 문제 풀이

 

너비 우선 탐색은 이동할 수 있는 모든 방향으로 한 번씩 이동하기 때문에, 가장 먼저 목적지에 도달하는 경로가 가장 빠른 거리도 됩니다.

 

너비 우선 탐색법을 코드로 작성하면 다음과 같습니다.

여기서는 정점과 정점까지 이동하는 거리를 함께 저장하는 VCNT 변수를 사용했습니다.

typedef short MTYPE;
typedef pair<MTYPE, MTYPE> VCNT;	// 정점과 이동한 거리

// 정점 R 부터 마지막 정점 N*M-1 까지의 거리를 반환하는 너비 우선 탐색
MTYPE BFS( MTYPE R){

    queue<VCNT> qu;

    VCNT vc(R, 1);	// VCN은 정점과 이동한 거리 pair
    qu.push(vc);

    visited[R] = true;

    while( !qu.empty()){

        VCNT& vc = qu.front();
        MTYPE v = vc.first;
        MTYPE cnt = vc.second;	// 현재까지 이동한 거리

        qu.pop();

        if ( v == N*M-1){	// 목표 정점까지 도달하면 거리를 반환
            return cnt;
        }

        for( MTYPE x : graph[v]){
            if (!visited[x]){
                visited[x] = true;
                VCNT vc(x, cnt+1);	// 거리를 1 늘려저 저장
                qu.push(vc);
            }
        }
    }

    return 0;
}

 

이제, 작성한 함수를 호출만 하면 문제 해결입니다.

// 그래프를 구성하기 위해 사용했던 플래그 초기화
memset(visited, 0, sizeof(bool)*SIZE*SIZE); 

// 정점 0부터 N*M-1 정점까지 너비 우선 탐색
int cnt = BFS(0);	

cout << cnt;	// 최단 이동 거리 출력

 

 

소스 코드

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

#define SIZE 100

typedef short MTYPE;
typedef pair<MTYPE, MTYPE> VCNT;

bool visited[SIZE*SIZE];
vector<MTYPE> graph[SIZE*SIZE];

int N, M;

void AddEdge( MTYPE i1, MTYPE j1, MTYPE i2, MTYPE j2){
    MTYPE v1 = i1*M + j1;
    MTYPE v2 = i2*M + j2;

    graph[v1].push_back(v2);
    graph[v2].push_back(v1);
}

inline bool& IsExist(MTYPE i, MTYPE j){
    return visited[i*M+j];
}

MTYPE BFS( MTYPE R){

    queue<VCNT> qu;

    VCNT vc(R, 1);
    qu.push(vc);

    visited[R] = true;

    while( !qu.empty()){

        VCNT& vc = qu.front();
        MTYPE v = vc.first;
        MTYPE cnt = vc.second;

        qu.pop();

        if ( v == N*M-1){
            return cnt;
        }

        for( MTYPE x : graph[v]){
            if (!visited[x]){
                visited[x] = true;
                VCNT vc(x, cnt+1);
                qu.push(vc);
            }
        }
    }

    return 0;
}

int main(){

    scanf("%d %d", &N, &M);

    char str[SIZE+1] = {'\0'};
    bool bExist;
    for( int i = 0; i < N; i++){

        scanf( "%s", str);

        for( int j = 0; j < M; j++){
            bExist = false;
            if (str[j] == '1')
                bExist = true;

            IsExist(i, j) = bExist;
            
            if ( bExist){

                if ( j > 0 && IsExist(i, j-1)){
                    AddEdge(i, j-1, i, j);
                }
                if ( i > 0 && IsExist(i-1, j)){
                    AddEdge(i-1, j, i, j);
                }
            }
        }
    }

    memset(visited, 0, sizeof(bool)*SIZE*SIZE); // 플래그 초기화

    int cnt = BFS(0);

    cout << cnt;
    
    return 0;
}