[C++] 1613 - 역사 (골드 3)
1. 문제 설명
푸는데 시간을 많이 소모하긴 했지만, 재밌는 문제라서 오히려 좋은 시간이었다.
2. 아이디어
보자마자 Union-find 문제라고 생각해서 15분 만에 기계적으로 코드 작성해서 제출했다.
하면서 '나...좀 천재?'이러고 있었는데,
지금 생각해보면 왜 틀린 것도 아니고, 런타임 에러가 났는지가 의문이다.
여튼 50%까진 성공했으니, 배열 크기를 잘못 잡았나 싶어서 어떤 케이스에서 오작동이 되나 살펴보던 중
그냥 아이디어 자체가 틀렸음을 알게 되었다.
예제 입력이야 Union-find로 슥삭하고 풀리겠지만,
두 번째 케이스가 나오면 4, 5번 노드는 더 이상 하나의 집합으로 분리할 수가 없다.
즉, 트리를 만들어서 노드 간의 선행 관계를 따져야 하는 게 되는데 다음과 같은 선택지들이 있다.
(0 < N <= 400 , 0 < K <= 50,000 , 0 < S <= 50,000)
- DFS, 혹은 BFS
- DFS를 인접 행렬로 만들면 O(V^2), 인접 리스트로 만들면 O(V+E)
- 인접 행렬 방식으로 수행 하면, O(S*V^2)이므로 시간 초과 우려.
- 할 거면 인접 리스트로 하던가, 미리 선행 관계를 조사해서 최적화가 가능하다면 통과할 수 있을 지도?
- 근데 인접 리스트로 하는 것도 생각해보니 골치 아플 것 같다. 정방향으로 타는 경우와 역방향으로 타는 경우도 구분해줄 필요가 있을 거 같은데 되려나?
- 플로이드 워셜
- 여러 정점에서 다른 모든 정점까지의 최단 거리를 구하는 건데, 최단 거리는 알 필요 없고 갱신이 됐는지만 안 됐는지만 알면 된다. (연결이 안 되어 있으면 INF 값을 가지고 있을 것이므로)
- O(V^3)의 시간 복잡도를 가지므로 반드시 통과한다.
혹시나 내가 생각한 방법 말고 더 있나 싶어 다른 블로그들 찾아 보니 죄다 플로이드 워셜로 풀고 있던데,
마치 이 문제를 플로이드 워셜로 풀어야만 하는 듯한 말들을 많이 해서 bfs로 풀어보기로 했다.
(그리고 플로이드 워셜로 풀어버리면 너무 쉽잖아..재미없을 거 같다.)
bfs로 해결하면 시간 초과가 나는 이유가 O(S*V^2), 즉 S번 bfs를 반복해야 하기 때문이다.
그런데 이렇게 하나의 문제에 대해 여러 테스트 케이스를 돌려보는 문제는 처음부터 답을 다 찾아두고,
마지막엔 인덱스 조회만 해서 풀이하는 방식으로 종종 해결 가능한 경우가 많다.
그 말은 즉슨, bfs를 s에 대해서 뒤져볼 게 아니라, 처음부터 정점 간의 관계성을 모두 파악해두기만 하면 끝난다는 얘기다.
1️⃣ 입력
void init() {
cin >> n >> k;
for (int i=0; i<k; ++i) {
int early, later; cin >> early >> later;
adj[early][later] = -1;
adj[later][early] = 1;
}
}
처음에는 일단 정방향, 역방향에 대해 모두 저장해두자.
다만 이 정보는 현재 정점과 직접 연결된 정점에 대한 관계일 뿐이다.
2️⃣ queue 생성
queue<int> q;
for (int history=1; history<=n; ++history) {
vector<bool> visited; visited.resize(n+1);
for (int item=1; item<=n; ++item)
if (adj[history][item] == -1)
q.push(item);
bfs(history, visited, q);
}
현재 노드의 하위 노드에 속하는 정점을 모두 queue에 넣어버리고 bfs를 수행한다.
bfs의 output은 현재 노드에 연결된 모든 하위 노드를 파악하여 adj를 업데이트 해야 한다.
- 이 문제에서 이전 역사가 얼마나 격차가 발생하는지에 대한 비용은 전혀 관심없다. 단순히 선행/후행 관계만을 파악하면 된다.
- 사건 전후 관계가 모호한 경우는 없으므로, 별도의 예외 처리를 필요로 하지 않는다.
3️⃣ 관계 매핑
void bfs(int target, vector<bool> &visited, queue<int> &q) {
while (q.size() > 0) {
int now = q.front(); q.pop();
if (visited[now]) continue;
visited[now] = true;
if (adj[target][now] != -1) {
adj[target][now] = -1;
adj[now][target] = 1;
}
for (int item=1; item<=n; ++item)
if (!visited[item] && adj[now][item] == -1)
q.push(item);
}
}
지금부터 target 노드를 기준으로 모든 하위 노드를 탐색한다.
연결되어 있는 모든 노드에 대해 선행/후행 노드 정보를 갱신한다.
4️⃣ 조회
cin >> s;
for (int i=0; i<s; ++i) {
int a, b; cin >> a >> b;
cout << adj[a][b] << "\n";
}
마지막은 업데이트된 정보를 조회만 하면 끝난다.
O(VE)로 해결한 사람이 있지 않을까 싶어서 찾아보긴 했는데,
예상대로 이 문제의 정해로 예상되는 풀이를 사용하면 O(NK)로 풀이가 가능하다고 한다.
난 트리 만들기 귀찮아서 인접 행렬로 밀어버렸다.
3. 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
int n, k, s;
void init();
void bfs(int, vector<bool>&, queue<int>&);
int adj[410][410];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
init();
queue<int> q;
for (int history=1; history<=n; ++history) {
vector<bool> visited; visited.resize(n+1);
for (int item=1; item<=n; ++item)
if (adj[history][item] == -1)
q.push(item);
bfs(history, visited, q);
}
cin >> s;
for (int i=0; i<s; ++i) {
int a, b; cin >> a >> b;
cout << adj[a][b] << "\n";
}
}
void init() {
cin >> n >> k;
for (int i=0; i<k; ++i) {
int early, later; cin >> early >> later;
adj[early][later] = -1;
adj[later][early] = 1;
}
}
void bfs(int target, vector<bool> &visited, queue<int> &q) {
while (q.size() > 0) {
int now = q.front(); q.pop();
if (visited[now]) continue;
visited[now] = true;
if (adj[target][now] != -1) {
adj[target][now] = -1;
adj[now][target] = 1;
}
for (int item=1; item<=n; ++item)
if (!visited[item] && adj[now][item] == -1)
q.push(item);
}
}