[BOJ 4324 // C++] XYZZY

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 4324번 문제인 XYZZY이다.
문제는 아래 링크를 확인하자.

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

4324번: XYZZY

 

먼저 1번 방에서 \(N\)번 방까지 도달하기 위해 움직여야 하는 횟수가 상당히 많을 수 있음을 확인하자. 예를 들어 1번부터 50번 방까지로 이루어진 사이클 형태의 경로를 따라 한 바퀴 돌 때마다 에너지가 1씩 증가하고, 각각 에너지가 100씩 감소하는 51~99번 방을 거쳐 100번 방으로 도착해야 하는 형태의 그래프의 경우 거쳐야 하는 방의 수가 매우 많을 것이다. 이 문제는 한 실행에 여러 테스트케이스를 해결해야하므로, 위의 내용과 함께 생각해보면 도착할 때까지 직접 시뮬레이션을 돌리는 것은 적절한 풀이가 아닐 것이라고 결론내릴 수 있다.

위의 풀이가 비효율적인 이유는 위와 같이 사이클을 여러 번 돌아 \(N\)번 방에 도달하게 되는 경우 직접 사이클을 도는 시뮬레이션 과정이 오래 걸리기 때문이다. 이 사이클을 직접 따라 돌면서 \(N\)번 방까지 가는 과정을 무조건 살펴봐야 할까?

그렇지 않다. 이 문제에서는 \(N\)번 방의 도달 가능성만을 구하면 되므로, 사이클을 돌아야 하는 경우 \(1\)번 방에서 도달 가능하면서 에너지가 증가하는 사이클에 속한 각 방으로부터 \(N\)번 방으로 도달할 수 있는지를 확인하는 것으로 문제를 해결할 수 있다.

사이클을 돌아야 하는 경우와 그럴 필요가 없는 두 경우 모두에 신경써 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <utility>
using namespace std;

int N, K;
int E[101];
vector<int> G[101], invG[101];
int HP[101], tmp[101], mxHP[101], oldmxHP[101];
int chk[101], visited[101], ans;

void dfs(int cur) {
	visited[cur] = 1;
	if (chk[cur]) ans = 1;
	for (auto &nxt:invG[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

void solve() {
	for (int i = 1; i <= N; i++) G[i].clear(), invG[i].clear();
	for (int i = 1; i <= N; i++) {
		cin >> E[i] >> K;
		G[i].clear();
		while (K--) {
			int x; cin >> x;
			G[i].emplace_back(x);
			invG[x].emplace_back(i);
		}
	}
	if (N == 1) {
		cout << "winnable\n";
		return;
	}

	memset(HP, 0xff, sizeof(HP));
	memset(mxHP, 0xff, sizeof(mxHP));
	HP[1] = mxHP[1] = 100;
	for (int k = 0; k < N; k++) {
		memset(tmp, 0xff, sizeof(tmp));
		for (int cur = 1; cur <= N; cur++) {
			if (HP[cur] < 0) continue;
			for (auto &nxt:G[cur]) {
				if (HP[cur] + E[nxt] < 1) continue;
				tmp[nxt] = max(tmp[nxt], HP[cur] + E[nxt]);
			}
		}
		swap(HP, tmp);
		if (HP[N] > 0) {
			cout << "winnable\n";
			return;
		}
		for (int i = 1; i <= N; i++) mxHP[i] = max(mxHP[i], HP[i]);
	}
	for (int i = 1; i <= N; i++) oldmxHP[i] = mxHP[i];
	for (int k = 0; k < N; k++) {
		memset(tmp, 0xff, sizeof(tmp));
		for (int cur = 1; cur <= N; cur++) {
			if (HP[cur] < 0) continue;
			for (auto &nxt:G[cur]) {
				if (HP[cur] + E[nxt] < 1) continue;
				tmp[nxt] = max(tmp[nxt], HP[cur] + E[nxt]);
			}
		}
		swap(HP, tmp);
		if (HP[N] > 0) {
			cout << "winnable\n";
			return;
		}
		for (int i = 1; i <= N; i++) mxHP[i] = max(mxHP[i], HP[i]);
	}
	memset(chk, 0, sizeof(chk));
	for (int i = 1; i <= N; i++) {
		if (mxHP[i] > oldmxHP[i]) chk[i] = 1;
	}
	memset(visited, 0, sizeof(visited)), ans = 0;
	dfs(N);
	if (ans) cout << "winnable\n";
	else cout << "hopeless\n";
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N > 0) {
		solve();
		cin >> N;
	}
}