[백준] 2178번 : 미로 탐색(BFS) - C++

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

2178번: 미로 탐색

---

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

#define MAX 100
int map[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];
int N,M;
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
queue<pair<int, int>> q;

void reset()
{
    for(int i = 0;i<MAX;i++)
        for(int j = 0 ; j<MAX;j++)
            visited[i][j] = 0;
}

void BFS(int a, int b)
{
    visited[a][b] = true;
    dist[a][b] += 1;
    q.push(pair<int,int>(a,b));
    while(!q.empty())
    {
        a = q.front().first;
        b = q.front().second;
        q.pop();
        
        for(int i = 0;i<4;i++)
        {
            int tmpa = a+dir[i][0];
            int tmpb = b+dir[i][1];
            
            if(( tmpa > 0 && tmpb > 0) && (tmpa <= N && tmpb <= M))
            {
                if(map[tmpa][tmpb] == 1 && !visited[tmpa][tmpb])
                {
                    visited[tmpa][tmpb] = true;
                    dist[tmpa][tmpb] = dist[a][b] + 1;
                    q.push(pair<int, int>(tmpa, tmpb));
                    
                }
            }
        }
    }
}

int main(void)
{
    cin >> N >> M;
    
    for(int i = 1; i<=N; i++)
    {
        string tmp;
        cin >> tmp;
        for(int j=1;j<=M;j++)
        {
            dist[i][j] = 0;
            map[i][j] = tmp[j-1] - '0';
        }
    }
    reset();
    BFS(1,1);
    cout<<dist[N][M];
}

최단거리 및 미로찾기 문제는 BFS로 해결하는 것이 좋다.

노드와 연결된 다음 노드를 찾기 위해서 dir이라는 배열을 사용해 주었다.

상하좌우로 움직이기 때문에 배열은 {{1,0},{-1,0},{0,-1},{0,1}}로 구성했다.

방문한 노드를 판별하기 위해서 visited라는 배열을 사용하였고, 지나야하는 칸 수를 세기 위해 dist라는 배열을 사용하였다.

 

처음에는 dist배열을 사용하지 않고 변수 num을 사용하였다. 예제 1은 num을 사용하여도 해결할 수 있었지만, 

예제 2는 다음과 같이 중복하여 이동할 때마다 num을 증가시켜 주었기 때문에 틀렸던 것 같다.

dist에는 이동한 거리를 누적하여 더해주었다.