https://www.acmicpc.net/problem/2423
요약
(0,0) 지점에서 (M,N) 지점으로 이어지는 회로를 만든다.
1. 미리 정해진 회로의 상태가 주어진다. 이때, 회로는 '/' 방향과 '\' 방향인 두 종류의 선으로 구성된다.
2. 정해진 방향의 회로를 따라 이동할 수도 있고, 이를 90도 회전시켜 방향을 돌린 뒤, 이동할 수 있다. 이때, 정해진 방향의 회로를 따라 이동할 때의 비용을 0, 방향을 회전시킨 뒤 이동하는 비용을 1로 하는 가중치 그래프를 떠올릴 수 있다.
3. 위와 같이 정점을 정한 뒤 '\' 방향일 때는 (j, i)에서 (j+1,i+1)로 향하는 무방향 간선을, '/' 방향일 때는 (j+1, i)에서 (j, i+1)로 향하는 무방향 간선을 설정하여 다익스트라로 풀이한다.
4. 다익스트라의 시간 복잡도는 $O\left ( \left| E\right|log\left|E \right| \right )$이고, 정점의 개수가 최대 500 * 500 = 250000개, 간선의 개수가 최대 2 * V이므로 1초 안에 처리 가능하다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, pair<int, int>> pii;
const int INF = 0x3f3f3f3f;
struct cmp {
bool operator() (pii A, pii B) {
return A.first > B.first;
}
};
int N, M;
vector <pii> graph[505][505];
int dist[505][505];
void Dijkstra(int start_x, int start_y);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
for (int j = 0; j < M; j++) {
if (s[j] == '/') {
graph[i][j + 1].push_back({ 0,{j,i + 1} });
graph[i + 1][j].push_back({ 0,{j + 1,i} });
graph[i][j].push_back({ 1,{j + 1, i + 1} });
graph[i + 1][j + 1].push_back({ 1,{j,i} });
}
else {
graph[i][j].push_back({ 0,{j + 1, i + 1} });
graph[i + 1][j + 1].push_back({ 0,{j,i} });
graph[i][j + 1].push_back({ 1,{j,i + 1} });
graph[i + 1][j].push_back({ 1,{j + 1,i} });
}
}
}
Dijkstra(0, 0);
if (dist[N][M] == INF) cout << "NO SOLUTION";
else cout << dist[N][M];
return 0;
}
void Dijkstra(int start_x, int start_y) {
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= M; j++) dist[i][j] = INF;
}
priority_queue <pii, vector<pii>, cmp> pq;
dist[start_y][start_x] = 0;
pq.push({ 0, {start_x, start_y} });
while (pq.size()) {
int x = pq.top().second.first;
int y = pq.top().second.second;
int val = pq.top().first;
pq.pop();
if (dist[y][x] < val) continue;
for (int i = 0; i < graph[y][x].size(); i++) {
int nx = graph[y][x][i].second.first;
int ny = graph[y][x][i].second.second;
int new_val = val + graph[y][x][i].first;
if (dist[ny][nx] > new_val) {
dist[ny][nx] = new_val;
pq.push({ new_val, {nx,ny} });
}
}
}
}
원글: https://int-p.tistory.com/9
'풀이 포스팅 > 3팀(목요일 20:00 ~)' 카테고리의 다른 글
[백준 17833번] 홍익대학교 지하캠퍼스, C++ 풀이 (1) | 2022.11.24 |
---|---|
[백준 20046번] Road Reconstruction, C++ 풀이 (0) | 2022.11.24 |
[백준 13912번] 외계 생물, C++ 풀이 (0) | 2022.10.08 |
[BOJ 16565번] N포커, C++ 풀이 (0) | 2022.10.07 |
[BOJ 1007번] 벡터 매칭, C++ 문제 풀이 (3) | 2022.09.29 |