[C++] 백준 11725번 - 그래프와 STL을 사용한 풀이

STL이 뭘까요?

Standard Template Library(STL)는 미리 만들어둔 자료구조를 모아둔 라이브러리예요. 예를 들어 많이 사용하는 자료구조로 linked list, stack 등이 있을텐데 이걸 개발자가 일일이 만드는 게 아니라 미리 만들어둔 걸 그대로 가져와서 사용할 수 있도록 하는 것이죠. 그래서 STL을 사용해서 처음부터 구현한다는 번거로움을 줄이고 개발할 수 있다는 장점이 있어요.

문제를 살펴볼까요?

먼저 N과 N-1개 간선(edge) 정보를 입력받은 후 2번 노드부터 시작해서 각 노드의 부모 노드 숫자를 차례대로 출력하도록 되어 있어요. 첫 번째 예시 입출력을 살펴보면서 문제를 이해해 볼까요?

 

 

예제 입력 1처럼 입력받으면 루트가 1인 트리가 다음과 같이 나타난다는 걸 알 수 있어요. 이 상태에서 출력은 2번 노드부터 시작해서 부모 노드 숫자를 차례대로 출력합니다. 2의 부모 노드는 4, 3은 6, 4는 1...처럼 진행해요.

어떻게 접근하면 좋을까요?

노드 2부터 차례대로 값을 출력해야 하니 예를 들어 arr[2]일 때 바로 값을 출력할 수 있으면 좋겠다는 생각이 들었어요. 하지만 트리를 구현하는 자료구조는 대부분 linked list로 위에서부터 내려오는 방식이어서 제가 원하는 방향성에 적절하지 않았죠.

 

그래서 그래프를 다루듯이 알고리즘을 생각해봤어요. 트리도 그래프의 일종이니까요. 이 점을 참고하셔서 아래 예시를 통해 제가 생각한 방법을 살펴보시면 좋겠어요.

1.

 

예제 입력 1처럼 먼저 N에 7이 들어왔을 때 7+1의 공간을 priority와 edge라는 배열에 마련해요. 여기서 priority는 루트일 때 1인 트리의 깊이(depth)를 뜻하고, edge는 각 노드에 연결된 다른 노드의 배열이 들어갈 거예요. priority는 루트를 제외한 나머지 값을 0으로 초기화해서 아직 입력되지 않았거나 서열이 잡히지 않았다는 걸 표시할 거예요.

2.

다음 순서로 1과 6이 들어왔을 경우 edge에 각 노드를 추가해요. 그리고 그 두 숫자는 세 가지 경우가 있을 수 있는데, a와 b라고 할 때 priority[b]만 0이 아닐지, priority[a]만 0이 아닐지, 아니라면 두 숫자 모두 0일 경우로 나눌 수 있어요.

 

위 예시는 a에 해당하는 1에 값이 있고 b에는 값이 없는 두 번째 경우에 해당해요. 따라서 이 때는 b에 1을 더한 2를 저장해줌으로써 깊이를 지정할 수 있어요. 이 과정은 첫 번째 경우도 같은 방식으로 할 수 있어요. 세 번째 경우는 뒤에서 자세히 설명할께요.

3.

 

동일한 방법으로 계속 진행해요.

4.

5.

위 방법이 가능했던 것은 입력 경우가 첫 번째와 두 번째 경우만을 충족했기 때문이에요. 그런데 만일 세 번째 경우처럼 입력받은 숫자 a와 b의 priority값이 모두 0이었다면 어떡할까요? 간단해요. 우선 edge 정보만 넣어두고 priority는 나중에 업데이트하는 걸로 미루면 되니까요. 만일 priority값을 가지는 숫자 a가 들어오면 edge[a][i]를 재귀적으로 살펴보는 방법으로 문제를 해결할 수 있어요.

소스코드

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

vector<int> priority;
vector<vector<int>> edge;

void prioritizing_vertexes(int &a, int &b) {
    if (priority[a] && !priority[b]) {
        priority[b] = 1 + priority[a];
        for (int connected : edge[b]) {
            if (!priority[connected]) {
                prioritizing_vertexes(b, connected);
            }
        }
    } else if (priority[b] && !priority[a]) {
        priority[a] = 1 + priority[b];
        for (int connected : edge[a]) {
            if (!priority[connected]) {
                prioritizing_vertexes(a, connected);
            }
        }
    }
}

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

    int N; cin >> N;
    priority.resize(N+1, 0);
    edge.resize(N+1);

    priority[1] = 1;

    int a, b;
    for (int i = 0; i < N-1; i++) {
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
        prioritizing_vertexes(a, b);
    }

    for (int i = 2; i <= N; i++) {
        for (int connected : edge[i]) {
            if (priority[connected] < priority[i]) {
                cout << connected << '\n';
                break;
            }
        }
    }
    return 0;
}