Coding Test/Solution

[C++] 1613 - 역사 (골드 3)

나죽못고나강뿐 2023. 11. 3. 15:03

1. 문제 설명

 

 

1613번: 역사

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.

www.acmicpc.net

푸는데 시간을 많이 소모하긴 했지만, 재밌는 문제라서 오히려 좋은 시간이었다.

 


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