백준 2665 - 미로 만들기

문제

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

리뷰

java가 아닌 c++로 풀이해보았다.

다익스트라로 풀이할 수 있는 전형적인 문제였다.

map에 검은방을 1, 흰방은 0으로 값을 넣고 dist 배열을 INT_MAX로
초기화한다음 그저 좌표별로 다익스트라를 돌리면 쉽게 답을 도출할 수 있었다.

로직의 시간복잡도는 다익스트라에서 $O(E \log V)$이기 때문에 최악의 경우
$E=50 \times 50 \times 4$, $V=50 \times 50$ 에서도 무난히 문제 제한 조건인
1초를 통과한다.

코드

#include<iostream>
#include<queue>
#include<array>
#include<algorithm>
#include<climits>
using namespace std;

int map[50][50];
int dist[50][50];

class Node{
public:
    int x, y, w;

    Node(int x, int y, int w) : x(x), y(y), w(w) {}

    bool operator>(const Node& other) const{
        return w>other.w;
    }
};

bool isOut(int x, int y, int n){
    return x<0 || x>=n || y<0 || y>=n;
}

void initDist(){
    for(auto & i : dist)
        fill(i, i+50, INT_MAX);
}

void dijkstra(int n){
    array<int, 4> dx={-1,1,0,0};
    array<int, 4> dy={0,0,-1,1};

    priority_queue<Node, vector<Node>, greater<>> minHeap;
    minHeap.push(Node(0,0,0));
    initDist();
    dist[0][0]=0;

    int nx, ny;

    while(!minHeap.empty()){
        Node current = minHeap.top();
        minHeap.pop();

        for(int i=0; i<dx.size(); i++){
           nx=current.x+dx[i];
           ny=current.y+dy[i];

           if(isOut(nx, ny, n))
               continue;

           if(dist[ny][nx]>current.w+map[ny][nx]){
               dist[ny][nx]=current.w+map[ny][nx];
               minHeap.push(Node(nx, ny, dist[ny][nx]));
           }
        }
    }
}

int main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    int n;
    cin>>n;
    cin.ignore();

    for(int y=0; y<n; y++){
        string line;
        getline(cin, line);
        for(int x=0; x<line.length(); x++)
            map[y][x]=line.at(x)=='1'?0:1;
    }

    dijkstra(n);

    cout<<dist[n-1][n-1];
}

결과