[C++]미로 만들기 [BOJ 2665]

문제를 살펴보면 딱히 어려운 문제는 아니다. 

그냥 다익스트라 2차원으로 돌리면된다. 

흰색이 1 검은색이 0이라는 점에 착안하면 검은색에 가중치를 두기 위해 필자는 원본을 toggle 해줬다. 

그냥 벡터도 필요없이 dst 2차원을 갱신해주며 다익스트라를 돌려주자
(요즘 너무 쉬운것만 올리는것 같다 - 맨날 이소리하고 맨날 쉬운거 올린다)

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

2665번: 미로만들기

2665번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 미로만들기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 2961 1257 858 42.644% 문제 n×n 바둑판 모양으로 총 n 2 개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어가 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으

www.acmicpc.net

<Code>

// pda_pro12
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
 
#define INT 0x7fffffff
#define N_ 51
 
using namespace std;
 
int n, a[N_][N_], dst[N_][N_], dx[] = { -1,1,0,0 }, dy[] = { 0,0,1,-1 };
priority_queue<pair<pair<int, int>, int>> pq;
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%1d", &a[i][j]);
            a[i][j] = (a[i][j] == 0) ? 1 : 0; 
            dst[i][j] = INT;
        }
    }
    dst[0][0] = 0;
    pq.push({ {0,0},0 });
    while (!pq.empty()) {
        int v_x = pq.top().first.first; int v_y = pq.top().first.second;
        int dis = -pq.top().second;
 
        pq.pop();
        if (dis > dst[v_x][v_y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = v_x + dx[i]; int ny = v_y + dy[i]; 
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; 
            int n_dis = dis + a[nx][ny]; 
            if (n_dis < dst[nx][ny]) {
                dst[nx][ny] = n_dis; 
                pq.push({ {nx, ny}, -n_dis });
            }
        }
    }
    cout << dst[n - 1][n - 1]; 
    return 0;
}