11725. 나무의 부모 찾기 – 실버 2

by

(실버 II) 나무의 아버지를 찾아서 – 11725

질문 링크

성능 요약

메모리: 10060KB, 시간: 44ms

분류

그래프 이론(graphs), 그래프 순회(graph_traversal), 트리, 너비 우선 순회(bfs), 깊이 우선 순회(dfs)

'추천 관련글,

문제 설명

뿌리가 없는 나무가 주어집니다.

이때 트리의 루트노드가 1로 설정되어 있을 때 각 노드의 부모노드를 찾는 프로그램을 작성한다.

입력하다

첫 번째 줄은 노드 수 N(2 ≤ N ≤ 100,000)을 제공합니다.

두 번째 줄부터 시작하여 트리에 연결된 두 꼭지점을 N-1 줄에 표시합니다.

인쇄

첫 번째 라인부터 N-1 라인, 노드 2부터 순차적으로 각 노드의 부모 노드 번호를 출력합니다.

문제를 풀다

질문을 통해 얻을 수 있는 정보는 다음과 같다.

  1. 번호 1에 뿌리를 둔 트리 구조를 사용하는 문제
  2. 최대 100,000개의 입력이 있을 수 있으므로 메모리 사용량 및 처리 시간에 주의하십시오.

노드 간 연결 정보를 활용하여 문제 분석
마침내 각 노드의 친노드 정보가지다 마련하다이것이 결과여야 합니다.

최대 100,000개의 입력 허용 지도 탐색이렇게 처리된다 시간 문제 다루기일어날 것이다
따라서 연결 정보를 저장하여 루트 1~에서 아래에계속할 필요가 있다고 판단

우선 단순한 1차원 배열의 연결 노드 정보를 저장하기 위해 자식 노드의 개수가 하나가 아닌 여러 개가 되는 문제가 있다.


따라서 배열의 각 요소에는 연결된 노드에 대한 정보를 저장하는 배열이 있어야 합니다.

이것을 해결 vector그리고 구조체를 사용하여 해결됩니다.

typedef struct node{
 std::vector<int> arr;
}node;

위 구조에 대한 인수로서의 배열node connect(100001)아래와 같은 구조로 사용하려고 합니다.

n번 노드 : connect 배열의 index
n번 노드와 연결된 노드 정보 : vector형태의 배열

마지막으로 각 노드는 입력을 받을 때 연결 정보를 가질 수 있습니다.

for (int i = 0; i < N-1; i++) {
    int num1, num2;
    std::cin >> num1 >> num2;
    connect(num1).arr.push_back(num2);
    connect(num2).arr.push_back(num1);
}

두 가지 정보가 있습니다.

  1. 노드 간 연결 정보
  2. 루트는 1입니다.

이것을 사용하는 방법 DFS 지침 재귀함수그것을 고치려고
프로세스는 다음과 같습니다.

  1. 1에 연결된 노드(n)를 찾습니다.

  2. 1에 연결된 노드(n)의 부모 노드 정보를 1로 설정(부모 노드 정보와 함께 어레이에 저장)
  3. 재귀 함수에 대한 인수로 n을 사용하여 함수 호출
  4. n에 연결된 노드를 찾아 부모 노드 정보를 n으로 설정

다만, arr 배열의 접속 정보에는, 부모노드와의 연결정보아직 가지고 있기 때문에
부모노드의 정보가 없는 노드만 처리 재귀 함수의 내부 분석나는해야한다.

상위 노드 정보 저장 head배열 사용 if문0개 노드만 처리됨 

void find_head(int head_num) {
    for (auto& e : connect(head_num).arr) {
        if (head(e) == 0) {
            head(e) = head_num;
            find_head(e);
        }
    }
    return;
}

마지막으로 위의 재귀 함수를 통해 DFS이것은 그것을 해결했습니다.


부모 노드 정보를 얻기 위해 트리 전체를 이동하는 방식이기 때문이다.

BFS당신은 또한 사용할 수 있습니다.

코드

#include<iostream>
#include<vector>
typedef struct node {
    std::vector<int> arr;
} node; // 입력받은 정수 저장 구조체

node connect(100001); // 입력받은 연결된 두 정점을 저장한 구조체 배열
int head(100001); // 각 숫자의 부모노드를 저장하는 배열
void find_head(int head_num); // DFS 방식으로 각 부모노드의 숫자를 저장

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

    int N;
    std::cin >> N;
    for (int i = 0; i < N-1; i++) {
        int num1, num2;
        std::cin >> num1 >> num2;
        connect(num1).arr.push_back(num2);
        connect(num2).arr.push_back(num1);
    }
    find_head(1);
    for (int i = 2; i <= N; i++) {
        std::cout << head(i) << '\n';
    }
    return 0;
}

void find_head(int head_num) {
    for (auto& e : connect(head_num).arr) {
        if (head(e) == 0) {
            head(e) = head_num;
            find_head(e);
        }
    }
    return;
}