백준 2665 미로만들기 - C++

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

이 문제는 시작 지점 (1,1) 부터 (N,N)까지 가는데 벽을 최대한 적게 부수며 갔을때, 부순 벽의 갯수를 구하는 문제이다.
이 문제는 다익스트라 또는 BFS로 풀 수있으며, 나는 BFS로 이 문제를 풀었다.
나는 BFS탐색을 할때, 우선순위 큐를 사용하여 벽의 갯수를 적게 부순 경우를 우선적으로 탐색하게 하였고, 그렇게 (N,N)까지 도착하였을때 부순 벽의 갯수를 출력하게 하였다.

소스코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n;
int map[51][51];
bool visited[51][51];

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

void bfs()
{
    priority_queue<pair<int,pair<int,int> >, vector<pair<int,pair<int,int > > > ,greater<pair<int,pair<int,int> > > > pq;
    pq.push(make_pair(0,make_pair(1,1)));       // 벽부순 횟수, 좌표 x , y
    visited[1][1] = true;                       // 시작지점은 방문처리.
    while (!pq.empty())
    {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int breakblock = pq.top().first;
        if (x == n && y == n)                  // 도착 지점 체크!
        {
            cout << breakblock;
            return ;
        }
        pq.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i]; 
            if (xx >= 1 && yy >= 1 && xx <= n && yy <= n && !visited[yy][xx])       // 방문안한 배열만 들어가기, 맵 범위 제한
            {
                if (map[yy][xx] == 0)           // 벽이면 벽을 부순횟수 1 추가하여 큐에 집어넣기 
                    pq.push(make_pair(breakblock+1,make_pair(xx,yy)));
                else            
                    pq.push(make_pair(breakblock,make_pair(xx,yy)));
                visited[yy][xx] = true;         // 방문처리 
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <=n; j++)
        {
            scanf("%1d",&map[i][j]);            // 연결된 문자열중 한개만 입력받기 위함.
        }
    }
    bfs();
    return 0;
}