백준 2178번 미로 탐색 C++

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

2178번: 미로 탐색

 

 

 

 

 문제 풀이

 미로가 주어진 경우에 최단 경로를 구하는 문제이다. 

 

 아주 간단하게 최단경로를 구하는 문제이므로 BFS를 생각해볼 수 있다. 미로 상태를 2차원 배열 map에 bool 형태로 저장해두고(1 : true, 0 : false) (1,1)에서부터 (N,M)까지 true인 경우에만 탐색을 진행하면 된다. 

 

 시행착오

 한 점으로 이동하는 방법이 여러가지일 수 있는데, 최소로 가는 경로로 업데이트 해주는 작업을 빼먹어서 값이 이상하게 나왔다. 다행히 한 번 컴파일 하고 알아차려서 디버깅하는데 시간이 적게 걸렸다.

 

코드

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

bool map[102][102];
int dis[101][101];

void bfs()
{
    queue<pair<int, int>> q;
    q.push(make_pair(1,1));
    dis[1][1] = 1;
    
    while(!q.empty())
    {
        pair<int,int> x;
        x = q.front();
        q.pop();
        
        if(map[x.first][x.second+1]&&dis[x.first][x.second+1] > dis[x.first][x.second] + 1)
        {
            dis[x.first][x.second+1] = dis[x.first][x.second] + 1;
            q.push(make_pair(x.first,x.second+1));
        }
        if(map[x.first+1][x.second]&&dis[x.first+1][x.second] > dis[x.first][x.second] + 1)
        {
            dis[x.first+1][x.second] = dis[x.first][x.second] + 1;
            q.push(make_pair(x.first+1,x.second));
        }
        if(map[x.first][x.second-1]&&dis[x.first][x.second-1] > dis[x.first][x.second] + 1)
        {
            dis[x.first][x.second-1] = dis[x.first][x.second] + 1;
            q.push(make_pair(x.first,x.second-1));
        }
        if(map[x.first-1][x.second]&&dis[x.first-1][x.second] > dis[x.first][x.second] + 1)
        {
            dis[x.first-1][x.second] = dis[x.first][x.second] + 1;
            q.push(make_pair(x.first-1,x.second));
        }
    }
}
int main()
{
    char state;
    int N,M,i,j;
    cin>>N>>M;
    
    for(i=1;i<=N;i++)
    {    
        for(j=1;j<=M;j++)
        {
            cin>>state;
            if(state == '1')
            {
                map[j][i] = true;
            }
        }
    }
    
    memset(dis,10000,sizeof(dis));
    bfs();
    cout<<dis[M][N];
}