[백준/C] 11725 - 트리의 부모 찾기

https://www.acmicpc.net/problem/11725
참고-트리 개념

---

트리

문제에서 '루트 없는 트리'라는 조건이 주어졌다. 트리는 사이클이 없이 모든 정점이 연결되어 있는 '그래프'라고 할 수 있기 때문에 루트가 없을 수 있다!

따라서 이 문제는 트리 문제이지만, 그래프 구현 문제라고도 할 수 있다.

---

구현 과정

먼저 정점 구조체와 연결리스트 구조체를 만든다.

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
} List;

DFS 함수를 만들기 위한 배열들도 전역으로 선언해준다.

int parents[100001];
int visited[100001];
List *graph;

주어진 두 정점 사이에 edge를 추가하는 addEdge 함수를 구현한다.

void addEdge(int a, int b) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = b;

    newNode->next = graph[a].head;
    graph[a].head = newNode;
}

이 함수를 통해 정점 a와 b가 아래처럼 연결되게 된다.

마지막으로 DFS 함수를 구현한다.

void dfs(int node) {
    visited[node] = 1;
    for (Node* p = graph[node].head; p != NULL; p = p->next) {
        int next = p->vertex;
        if (!visited[next]) {
            parents[next] = node;
            dfs(next);
        }
    }
}

현재 노드를 방문 표시하고, 인접한 노드를 순회하면서 방문되지 않은 노드에 대해 DFS를 재귀적으로 실행한다.

---

전체 코드

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
} list;

int parents[100001];
int visited[100001];
list *graph;

void addEdge(int a, int b) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex = b;

    newNode->next = graph[a].head;
    graph[a].head = newNode;
}

void dfs(int node) {
    visited[node] = 1;
    for (Node* p = graph[node].head; p != NULL; p = p->next) {
        int next = p->vertex;
        if (!visited[next]) {
            parents[next] = node;
            dfs(next);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

    graph = (list *)malloc(n * sizeof(list));

    for (int i = 1; i <= n; i++) {
        graph[i].head = NULL;
    }

    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
    }

    dfs(1);

    for (int i = 2; i <= n; i++) {
        printf("%d\n", parents[i]);
    }
    free(graph);
    return 0;
}

---

트리의 정의에 대해 다시 한 번 생각해볼 수 있었던 좋은 문제였다.