백준 2423번, 전구를 켜라 / Switch the Lamp On

 

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

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} });
			}
		}
	}
}