BOJ 2178 미로 탐색 - BFS

- (1,1)에서 (N,M)으로 가는 "가장 빠른 길"을 구하는 문제

- 가장 빠른 길을 구해야 할 때는 DFS 탐색은 사용X = 최단거리 보장X

- BFS는 모든 가중치가 1일때 좋은 성능을 보임

 

DFS, BFS => 목적은 모든 정점을 한번 씩 방문한다

 

- 최단거리를 구하기 위해 dist[][] 를 만들어 거리 저장

 

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

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

int map[110][110];
int visited[110][110];
int dist[110][110];
int n,m;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

//최단 경로이기 때문에 bfs 이용
int main(void){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d", &map[i][j]);
            visited[i][j]=0;
        }
    } // 입력 끝.

    queue<pair<int, int> > q;
    q.push(make_pair(0,0));
    dist[0][0] = 1;
    visited[0][0] = 1;

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

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx>=0 && nx<n && ny>=0 && ny<m){
                if(map[nx][ny]==1 && visited[nx][ny]==0){
                    q.push(make_pair(nx,ny));
                    dist[nx][ny] = dist[x][y] + 1;
                    visited[nx][ny] = 1;
                }
            }
        }
    }
    
    printf("%d", dist[n-1][m-1]);
}