[백준] 2178. 미로탐색

[문제]

 

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

[풀이]

 

미로의 정보가 입력으로 주어지고 시작점 (1,1)에서 도착점(N,M)까지의 최단거리를 구하는 문제이다.

1은 이동할 수 있는 칸을 의미하고, 0은 이동할 수 없는 칸을 의미한다. 

 

BFS를 사용해 풀었다. 다음 위치의 값이 1인 경우에만 좌표를 queue에 저장하였고, 이미 방문했던 곳이라면 queue에 담지 않았다.

실수했던 부분이 BFS는 동시에 움직이므로 최단거리를 구하는 경우 재방문 하지 않아도 된다.

 

[코드]

 

시간 : 0ms

#include <iostream>
#include <queue>
#define MAX 100

using namespace std;

int visited[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int N,M;

int dx[4]= {-1,1,0,0};
int dy[4] = {0,0,1,-1};

struct pos{
    int x,y;
};

int BFS()
{
    queue <pos> q;
    
    q.push({0,0});
    visited[0][0]=1;
    
    while(!q.empty()){
        
        int x= q.front().x;
        int y= q.front().y;
        if(x==N-1 && y==M-1)    break;
        q.pop();
        
        for(int i=0;i<4;i++){
            
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx <0 || ny<0 || nx >= N || ny >= M || map[nx][ny]==0)    continue;
            if(visited[nx][ny]!= 0 )   continue;
            
            visited[nx][ny] = visited[x][y]+1;
            q.push({nx,ny});
        }
    }
    
    return visited[N-1][M-1];
}

int main(void)
{
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    cout << BFS();
    
    return 0;
    
}