[구름 알고리즘 먼데이 챌린지] Week7 : 4. 이상한 미로

문제

구름이는 이상한 미로에 갇혔다. 미로는 N개의 방과 M개의 복도로 이루어져 있고, 각 방에는 1부터 N까지의 번호가 붙어 있다. 그리고 각 방의 바닥에는 1부터 10사이의 정수 Ai가 쓰여있다.

 

이 이상한 미로에는 이상한 규칙들이 있다.

• 방에서 움직이는 데 걸리는 시간은 고려하지 않는다.
• 미로에 있는 모든 복도는 양방향으로 이동할 수 있고, 복도마다 지나가는 데 걸리는 시간이 정해져 있다.
• i번 방과 j번 방이 복도로 직접 연결되어 있고, j번 방과 k번 방이 복도로 직접 연결되어 있을 때, 두 복도를 이용해 i번 방에서 k번 방으로 이동하려면 i를 Ai로 나눈 나머지와 k를 Aj로 나눈 나머지가 같아야 한다.

구름이는 현재 1번 방에 있고, 탈출구는 N번 방에 있다. 구름이가 이 이상한 미로에서 탈출할 수 있는지, 탈출할 수 있다면 구름이가 탈출하기까지 최소 얼마나 시간이 걸리는지 구해보자. 단, 맨 처음에 이용하는 복도는 위의 조건과는 상관 없이 원하는 복도를 이용할 수 있다.

---

입력

첫째 줄에는 이상한 미로에 있는 방의 개수 N(3 <= N <= 100,000), 복도의 개수 M(0 <= M <= 200,000)이 공백으로 구분되어 주어진다.

 

두 번째 줄에는 N개의 정수 A1,A2...AN이 공백으로 구분되어 주어진다. Ai는 i 번 방의 바닥에 적혀있는 수를 의미한다.

 

다음 M개의 줄에는 한 줄에 하나씩 복도의 정보를 의미하는 세 정수 u,v,w가 공백으로 구분되어 주어진다.

u와 v (1 <= u, v <= N)는 복도가 연결하고 있는 두 방의 번호를 의미하고, w(1 <= w <= 10^9)는 그 복도를 통과하는 데 걸리는 시간을 의미한다.

---

문제를 읽고 다익스트라 문제로 판단했다.

다익스트라 알고리즘에 "i번 방과 j번 방이 복도로 직접 연결되어 있고, j번 방과 k번 방이 복도로 직접 연결되어 있을 때, 두 복도를 이용해 i번 방에서 k번 방으로 이동하려면 i를 Ai로 나눈 나머지와 k를 Aj로 나눈 나머지가 같아야 한다." 라는 조건에 유의하며 구현하였다.

일단 다익스트라 구현을 위해 우선순위큐를 사용하는데 c++에서 priority_queue는 defalut로 max heap의 구조를 가지기 때문에 min heap으로 생성해 주었다.

또한, 보통 우선순위큐를 현재 노드 번호와 누적 가중치를 가지는 pair타입으로 생성해주는데

이 문제의 경우 특수 조건을 위해 이전 노드 번호를 함께 저장하기 위해 tuple타입으로 생성해주었다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
typedef long long ll;
const ll INF = 100000000000000;
int n, m, u, v, bottom[100001];
ll w;
vector<pair<int, ll>> edge[100001];
vector<ll> d(100001, INF);

void dijkstra() {
	int cur, prev, next;
	ll curd, nextd;
	//greater : min heap으로 우선순위큐 생성
	priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
	d[1] = 0;
	pq.push({ 0, 1, 0 });
	while (!pq.empty()) {
		curd = get<0>(pq.top());
		cur = get<1>(pq.top());
		prev = get<2>(pq.top());
		pq.pop();
		if (curd > d[cur]) continue;
		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i].first;
			//특수 조건을 만족하는 지 검사
			int comp1 = next % bottom[cur];
			int comp2 = prev % bottom[cur];
			if (cur != 1 && comp1 != comp2) continue; //바닥 값이 다르면 pass
			nextd = curd + edge[cur][i].second;
			if (d[next] > nextd) {
				d[next] = nextd;
				pq.push({ nextd, next, cur});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> bottom[i];
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		edge[u].push_back({ v, w });
		edge[v].push_back({ u, w });
	}
	dijkstra();
	//목적지 N에 도달하지 못할 경우 d[n]은 초기값 INF를 가짐
	if (d[n] == INF) cout << -1;
	else cout << d[n];
	return 0;
}

 

 

하지만 위 코드로 제출 시 11, 14, 22, 24, 25, 28, 31, 33 케이스에서 FAIL이 발생했다.

해설 풀이를 보고 위 로직이 틀렸음을 이해할 수 있었는데, 결론부터 말하자면 d배열은 현재 위치와 이전 위치를 저장할 수 있는 2차원 배열 형태이어야 한다.

아래 예시를 통해 자세히 살펴보자.

N = 4, M = 5, A = [3, 2, 3, 5]이고 u,v, w는 아래와 같다고 하자.

1 2 5 

2 4 6

2 3 3

1 3 13

4 3 7

이와 같은 경우 위 로직대로 수행하면 1 > 2 > 3 순서로 이동하며 d[3]은 8로 갱신되고

이후 3 > 4의 이동은 아래와 같이 조건에 부합하지 않기 때문에 불가능하다.

2(prev) % 3 = 2

4(next) % 3 = 1

2 != 1

이와 달리 1 > 3 > 4는 조건에 부합하면서 4에 도달할 수 있는데,

1 > 2 > 3에 의해 d[3]이 8로 갱신되었기 때문에 실질적으로 3 > 4에 이동을 수행하지 않게 된다.

이 때문에 배열 d는 d[cur][prev]와 같이 2차원 형태로 생성해 주어야 하는 것이다.

 

따라서 d를 2차원 배열로 생성하여 아래와 같이 구현하였다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
typedef long long ll;
const ll INF = 100000000000000;
int n, m, u, v, bottom[100001];
ll w, ans = -1;
vector<pair<int, ll>> edge[100001];
vector<vector<ll>> d(100001, vector<ll>(100001, INF));

void dijkstra() {
	int cur, prev, next;
	ll curd, nextd;
	priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
	d[1][0] = 0;
	pq.push({ 0, 1, 0 });
	while (!pq.empty()) {
		curd = get<0>(pq.top());
		cur = get<1>(pq.top());
		prev = get<2>(pq.top());
		pq.pop();
		if (curd > d[cur][prev]) continue;
		if (cur == n) { ans = curd; break; }
		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i].first;
			int comp1 = next % bottom[cur];
			int comp2 = prev % bottom[cur];
			if (cur != 1 && comp1 != comp2) continue; //바닥 값이 다르면 pass
			nextd = curd + edge[cur][i].second;
			if (d[next][cur] > nextd) {
				d[next][cur] = nextd;
				pq.push({ nextd, next, cur});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> bottom[i];
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		edge[u].push_back({ v, w });
		edge[v].push_back({ u, w });
	}
	dijkstra();
	cout << ans;
	return 0;
}

 

하지만, d를 2차원 배열로 생성하였을 때 런타임 에러가 발생했다.

 

이는 문제에서 제한하고 있는 메모리 크기를 초과하며 발생하는 것으로 생각된다.

해설을 보면 사실 배열 d는 100001 * 100001의 크기를 가질 필요가 없는데, 바닥 값이 1~10의 정수를 가지기 때문이다.

이는 해설에서도 자세히 설명해주고 있는데,

모든 정점의 A값이 1이고 그래프가 아래와 같이 구성되어 있다고 가정해 보자.

이 경우 가운데 5번 정점에 주목해 보면

1 > 2 > 5 > 6 > 9

1 > 2 > 5 > 7 > 9

1 > 2 > 5 > 8 > 9

1 > 3 > 5 > 6 > 9

1 > 3 > 5 > 7 > 9

1 > 3 > 5 > 8 > 9

1 > 4 > 5 > 6 > 9

1 > 4 > 5 > 7 > 9

1 > 4 > 5 > 8 > 9

와 같이 이동할 수 있는 경로는 9가지 된다.

잘 생각해 보면 우리가 다음 노드(=next)로 이동 시 현재 노드(=cur)를 유지했던 이유는 next에서 다시 이동 가능한 노드를 탐색할 때 next기준으로 다음 노드(=Next)가 조건에 부합하는, 이동 가능한 노드인지 검사하기 위함이었다.

 

따라서, next로 이동시 현재노드 자체를 저장하는 것 대신 cur % A[next] 값을 저장해 주어도 조건 검사가 가능함과 동시에 이렇게 해줄 경우 위와 같은 경우 탐색을 더 효율적으로 할 수 있게 된다.

또한, 바닥값은 1에서 10의 값을 갖기 때문에 2차원 배열 또한 100001 * 100001 의 크기가 아니라 100001 * 10이 될 수 있는 것이다.

현재 노드 cur이 1~100,000 중 어떤 수도 바닥값 1~10으로 모듈려 연산을 해준 값은 0~9를 벗어 날 수 없기 떄문이다.

ex)cur % A[next]

cur  % 1 = 0

cur  % 2 = 0 or 1

cur  % 3 = 0 or 1 or 2

cur  % 4 = 0 or 1 or 2 or 3

.

.

.

cur  % 10 = 0 or 1 or 2 or ... or 9

 

전체 소스 코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
typedef long long ll;
const ll INF = 100000000000000;
int n, m, u, v, bottom[100001];
ll w, ans = -1;
vector<pair<int, ll>> edge[100001];
vector<vector<ll>> d(100001, vector<ll>(10, INF));

void dijkstra() {
	int cur, prev, next;
	ll curd, nextd;
	priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
	d[1][0] = 0;
	pq.push({ 0, 1, 0 });
	while (!pq.empty()) {
		curd = get<0>(pq.top());
		cur = get<1>(pq.top());
		prev = get<2>(pq.top());
		pq.pop();
		if (curd > d[cur][prev]) continue;
		if (cur == n) { ans = curd; break; }
		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i].first;
			int comp1 = next % bottom[cur];
			int comp2 = prev % bottom[cur];
			if (cur != 1 && comp1 != comp2) continue; //바닥 값이 다르면 pass
			nextd = curd + edge[cur][i].second;
			if (d[next][cur % bottom[next]] > nextd) {
				d[next][cur % bottom[next]] = nextd;
				pq.push({ nextd, next, cur % bottom[next] });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> bottom[i];
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		edge[u].push_back({ v, w });
		edge[v].push_back({ u, w });
	}
	dijkstra();
	cout << ans;
	return 0;
}