[백준/C++] 15942번: 전구를 켜라(G2)

문제

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

2423번: 전구를 켜라

 

 

사용한 알고리즘

2022.02.14 - [PS/Algorithm] - [알고리즘 개념정리] 10. 최단경로 알고리즘

-> 다익스트라

 

 

풀이

타일 말고 꼭짓점을 기준으로 생각해보자.
(0,0)에서 (n,m)까지 가는 최단경로를 구하면 된다.

타일들이 간선역할을 한다고 생각하고,
타일을 회전시키지 않아도 만들어지는 연결은 가중치 0,
타일을 회전시켜야 만들어지는 연결은 가중치 1로 간선을 모델링한다.

이때, 2차원 좌표로 나온 정점을 1차원으로 보면 더 간편하게 풀 수 있다.
x, y값 상한이 k라면 (x,y)를 (k+1)*x + y 로 치환한다.

따라서, 0에서 시작하여 (k+1)*n + m 까지의 최단거리를 다익스트라로 구하면 된다.

 

전형적인 다익스트라 문제처럼 구현하면 되고, 간선 모델링 부분만 주의하면 된다. 
예를들어 살펴보자.
만약, i=2, j=3인 타일을 보고있을때 그 타일 모양이 '/'라면,
adj[(2,3)].push_back({(3,4), 1});
adj[(3,4)].push_back({(2,3), 1});
adj[(2,4)].push_back({(3,2), 0});
adj[(3,2)].push_back({(2,4), 0});
을 하면 된다. 이때, (2,3)은 (k+1)*2 + 3을 의미함.

 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
const int MAX_V=300001;
int n,m,k=501;
vector<pair<int,int>> adj[MAX_V];

int dijkstra(int st, int ed){
    int dist[MAX_V];
    fill(dist, dist+MAX_V, INT_MAX);
    int visited[MAX_V] = {0};
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; //min heap {dist, 정점}

    dist[st]=0;
    pq.push({0,st});
    while(!pq.empty()){
        int cur=pq.top().second; pq.pop();
        if(visited[cur]) continue; //이미 방문한 곳이면 무시
        visited[cur]=1;
        for(auto &u:adj[cur]){
            int next=u.first, cost=u.second;
            int next_dist = dist[cur]+cost;
            if(dist[next]>next_dist){
                //최단거리 갱신
                dist[next]=next_dist;
                pq.push({dist[next], next});
            }
        }
    }
    return dist[ed];
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>m;
    string s;
    for(int i=0; i<n; i++){
        cin>>s;
        for(int j=0; j<m; j++){
            if(s[j]=='/'){
                adj[i*k+j].push_back({(i+1)*k+(j+1),1});
                adj[(i+1)*k+(j+1)].push_back({i*k+j,1});
                adj[(i+1)*k+j].push_back({i*k+(j+1),0});
                adj[i*k+(j+1)].push_back({(i+1)*k+j,0});
            }
            else{
                adj[i*k+j].push_back({(i+1)*k+(j+1),0});
                adj[(i+1)*k+(j+1)].push_back({i*k+j,0});
                adj[(i+1)*k+j].push_back({i*k+(j+1),1});
                adj[i*k+(j+1)].push_back({(i+1)*k+j,1});
            }
        }
    }
    int ans=dijkstra(0, n*k+m);
    if(ans==INT_MAX) cout<<"NO SOLUTION";
    else cout<<ans;
    return 0;
}