[C++] 백준 2178 - 미로탐색

문제 - 미로탐색 (Silver1)

[백준 2178] https://www.acmicpc.net/problem/2178

풀이 전략

• 이 문제는 깊이우선탐색(DFS)와 너비우선탐색(BFS) 둘 다 풀 수 있다. 하지만, 경로의 경우의 수에 따라 DFS는 시간복잡도가 매우 커질 수 있으므로 BFS로 풀었다.
• 다른 경로 문제들 처럼 dx, dy를 설정하고, BFS 알고리즘에 x좌표와 y좌표를 pair로 큐에 집어넣는 거만 다르고 나머지는 일반적인 BFS 문제와 비슷하다.

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int dx[4]={1,0,-1,0}; // x좌표 이동
int dy[4]={0,1,0,-1}; // y좌표 이동

int N,M;
int Dist[101][101]; // 거리를 저장할 배열
char Map[101][101]; // 미로를 만들 배열
int visited[101][101]; // 방문한 위치를 표시할 배열

void BFS(int start_x, int start_y){
    visited[start_x][start_y]=1;

    queue<pair<int,int>> Q;
    Q.push(make_pair(start_x,start_y));

    while(!Q.empty()){
        int x=Q.front().first;
        int y=Q.front().second;

        Q.pop();

        for(int i=0;i<4;i++){
            int next_x=x+dx[i];
            int next_y=y+dy[i];
            if(next_x>=0 && next_x<N && next_y>=0 && next_y<M){
                if(Map[next_x][next_y]=='1' && visited[next_x][next_y]==0){
                    Dist[next_x][next_y]=Dist[x][y]+1; 
                    // 다음 위치로 이동
                    visited[next_x][next_y]=1;
                    // 방문했음 처리
                    Q.push(make_pair(next_x,next_y));
                    // 큐에 집어 넣어서 다음 좌표에서 BFS 시작
                }
            }
        }
        
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>M;

    for(int i=0;i<N;i++){
        cin>>Map[i];
    }
    BFS(0,0);
    cout<<Dist[N-1][M-1]+1<<'\n'; // 미로의 끝지점에서의 거리 출력
    return 0;
}

결과

결론

DFS, BFS는 정말 자주 쓰이는 알고리즘이라 코드를 외워서 응용하는 것도 나쁘지 않은듯?