[BOJ알고리즘, C++]#2665_미로 만들기, 최단 경로 알고리즘, 다익스트라 알고리즘

 

#1. 문제

2665번: 미로만들기

 

---

 

#2. 풀이

 

1. 다익스트라

[알고리즘]#2_길 찾기 알고리즘

 

[정의] : 다익스트라 알고리즘은 최단 경로 알고리즘 중 하나로, 가중치 그래프에서 임의의 출발 정점으로부터 다른 모든 노드 사이의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘은 '우선순위 큐'를 통해 구현 가능합니다.

 

2. 검은 방의 개수가 최소가 되는 최단 경로 찾기!

 

1. nxn의 2차원 vector 형식의 그래프를 구성합니다.
2. 출발 정점(graph [0][0])을 기준으로 다익스트라를 수행합니다. 이 과정에서 동, 서, 남, 북 방향으로 인접하며 접근 가능한 다음 방으로 탐색을 수행하며, 최종적으로 도착 지점(graph [N-1][N-1])의 최단 경로 값을 출력합니다.

 

---

 

#3. 코드

 

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

typedef pair<int,int> p;

int n;
vector<vector<int>> graph, dist;

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

int flip(int num)
{
    return num^1;
}

void dijkstra()
{
    priority_queue<pair<int, p>, vector<pair<int,p>>, greater<pair<int,p>>> pq;
    dist[0][0] = flip(graph[0][0]);
    pq.push({dist[0][0], {0,0}});
    
    while(!pq.empty())
    {
        p cur_vertex = pq.top().second;
        int cur_weight = pq.top().first;
        pq.pop();
        
        if(cur_weight > dist[cur_vertex.first][cur_vertex.second])
            continue;
        
        for(int i=0; i<4; ++i)
        {
            int ny = cur_vertex.first + dy[i];
            int nx = cur_vertex.second + dx[i];
            
            if(ny >= n || ny < 0 || nx >= n || nx < 0)
                continue;
            
            int new_dist = cur_weight + flip(graph[ny][nx]);
            if(dist[ny][nx] > new_dist)
            {
                dist[ny][nx] = new_dist;
                pq.push({new_dist, {ny, nx}});
            }
        }
    }
    
    cout << dist[n-1][n-1];
}
    
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    
    graph.resize(n, vector<int>(n));
    dist.resize(n, vector<int>(n, INT_MAX));
    
    for(int i=0; i<n; ++i)
    {
        string temp;
        cin >> temp;
        for(int j=0; j<n; ++j)
        {
            graph[i][j] = temp[j] - '0';
        }
    }
    
    dijkstra();
    
    return 0;
}

 

---