취미로 코딩하기

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

이번에 볼 문제는 백준 27451번 문제인 마키마씨가 정해주는 오늘 점심의 맛이다.
문제는 아래 링크를 확인하자.

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

문제에 주어진 셋이 같은 걸음수으로 도착할 수 있는 가장 가까운 칸과 그 경로를 출력하는 문제이다.

먼저, 세 명이 식당에 서있을 수 있는 경우의 수는 ${44}^3=85184$가지와 같음을 관찰하자. 따라서 0초부터 85184초까지 차례대로 매 초마다 각자 서있을 수 있는 곳을 따로따로 구하고 이를 통해 같은 칸에 셋이 동시에 있을 수 있는 가장 빠른 시간을 발견하는 것으로 문제를 해결할 수 있다. 단, 85184초까지 그러한 시각이 존재하지 않는다면 문제에서 요구하는 방법이 존재하지 않는 것이다.

매 초마다 다음 초에 서있을 수 있는 곳을 단순한 BFS와 같이 각 칸에서 이동할 수 있는 칸을 탐색한다면 $3\ast {44}^2$회의 에지를 살펴보게 되며(단, 이때의 횟수는 주어지는 그래프가 완전그래프임을 가정한 것이지만 실제 입력은 그렇게 주어질 수 없기는 하다.), 글쓴이는 이 작업이 1초 내에 완료될지 불안했다. 그래서 조금 더 효율적인 방법을 생각하게 되었다.

$N\le 44$임을 이용하면, 이러한 작업을 빠르게 하기 위해 각 식당에서 이동할 수 있는 다음 칸을 비트를 이용해 표현하는 전략을 사용할 수 있다는 점을 관찰할 수 있다. 글쓴이는 i번 식당에서 접근할 수 있는 식당목록 j들을 저장한 변수 edge[i]를 (1<<j)들을 전부 bitwise or한 값으로 저장하였다. 이와 같이 에지를 관리하면 매 초마다 다음 초에 각자가 있을 수 있는 위치를 구하는 속도를 크게 개선할 수 있음을 관찰하자.

또한, $(i,j,k)$를 노드로 갖는 모델의 그래프의 생성 방식을 생각해보면 최단경로의 길이는 85184가 될 수 없고 그보다 훨씬 짧을 것으로 예상되지만 그 upper bound의 구체적인 값을 계산하기는 쉽지 않아 이 방면으로 시간을 절약할 다음과 같은 다른 방법을 생각해보았다. 각자가 방문할 수 있는 위치의 집합의 3-tuple(이것 또한 85184가지 존재한다.)이 앞선 초에 등장한 적이 있다면 이 이후로는 앞서 나왔었던 3-tuple만이 반복해서 등장하게 될 것임을 알 수 있으므로 탐색을 종료하고 답이 없다고 판단할 수 있음을 이용해 탐색을 빠르게 종료할 수 있다. 각자가 방문할 수 있는 위치의 집합은 비트 표현을 이용하여 64비트 정수 하나를 이용해 표현할 수 있음을 확인하자.

최단경로를 실제로 구해내는 것은 해당 칸으로 오기 위해 이전 초에 있어야 하는 칸 중 하나를 저장하는, 백트래킹을 위한 테이블을 위 과정을 진행하며 채워 구해낼 수 있다.

여담으로 에디토리얼은 문제의 상황을 각자가 서 있는 위치로 나타낸 3-tuple $(i,j,k)$을 노드로, 각 노드의 상태와 1초 후에 있을 수 있는 상태 사이의 관계를 방향에지로 모델링해 해당 그래프에서 BFS를 돌리는 $O(N^6)$ 풀이를 제시하고 있으니 참고하자.

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

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

int N, M;
int A, B, C;
ll edges[45];
ll cur[3], nxt[3];
char backtrack[85185][45][3];
set<pair<ll, pair<ll, ll>>> st;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M >> A >> B >> C;
	while (M--) {
		int s, e; cin >> s >> e;
		edges[s] |= (1LL << e);
	}
	cur[0] = (1LL << A), cur[1] = (1LL << B), cur[2] = (1LL << C);

	for (int i = 1; i < 85185; i++) {
		for (int k = 0; k < 3; k++) {
			nxt[k] = 0;
			for (int j = 1; j <= N; j++) {
				if (cur[k] & (1LL << j)) {
					ll tmp = edges[j] & (~nxt[k]);
					if (tmp) {
						nxt[k] |= tmp;
						for (int jj = 1; jj <= N; jj++) {
							tmp >>= 1;
							if (tmp & 1) backtrack[i][jj][k] = j;
						}
					}
				}
			}

			cur[k] = nxt[k];
		}

		ll tmp = cur[0] & cur[1] & cur[2];
		if (tmp) {
			int idx = 0;
			while (!(tmp & (1LL << idx))) idx++;

			cout << idx << ' ' << i << '\n';
			for (int k = 0; k < 3; k++) {
				vector<int> ans;
				int pos = idx;
				for (int ii = i; ii > 0; ii--) {
					ans.emplace_back(pos);
					pos = backtrack[ii][pos][k];
				}
				ans.emplace_back(pos);

				while (!ans.empty()) {
					cout << ans.back() << ' ';
					ans.pop_back();
				}
				cout << '\n';
			}

			return 0;
		}

		pair<ll, pair<ll, ll>> p = make_pair(cur[0], make_pair(cur[1], cur[2]));
		if (st.count(p)) break;
		st.insert(p);
	}

	cout << -1;
}