본문 바로가기
Algorithm(BOJ, C)/Graph

[백준_11725] 트리의 부모 찾기 c

by kurooru 2024. 12. 7.
문제

컴파일에러 뭐냐고 ;; 이유 아시는분 알려주세요 제발

풀이
#include <stdio.h>
#define EXIT_SUCCESS    0
#define CONNECTED       1
#define MAX_NODE_NUM    100000
#define FIRST_NODE      0

// 각 노드의 부모 노드 기록 용
int parent[MAX_NODE_NUM] = { 0 };
// 연결 기록 용
char connection[MAX_NODE_NUM][MAX_NODE_NUM] = { 0 };
// n
int n;

/*
    자신의 자식 노드를 찾고, 찾은 경우 부모 노드에 기록
*/
void find_child(int curr_node)
{   
    // 현재 노드의 연결 관계를 탐색
    for (int i = 0; i < n; i++) {
        // 연결을 발견하면 (본인의 부모 노드인 경우 제외)
        if (connection[curr_node][i] && (i != parent[curr_node])) {
            // 부모로 기록
            parent[i] = curr_node;
            // 재귀
            find_child(i);
        }
    }
}

/*
    메인
*/
int main()
{   
    // 0) 입력
    scanf("%d", &n);
    
    for (int i = 0; i < n - 1; i++) {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
        connection[--v1][--v2] = CONNECTED;
        connection[v2][v1] = CONNECTED;
    }

    // 1) 루트 노드부터 자식 노드 찾기 시작 (자식 노드를 찾으면 해당 자식 노드는 본인의 부모 노드 기록)
    find_child(FIRST_NODE);

    // 2) 출력
    for (int i = 1; i < n; i++) {
        printf("%d\n", parent[i] + 1);
    }

    return EXIT_SUCCESS;
}

 

'Algorithm(BOJ, C) > Graph' 카테고리의 다른 글

[백준_1697] 숨바꼭질 c  (0) 2024.11.24
[백준_11403] 경로 찾기 c  (0) 2024.11.23
[백준_11724] 연결 요소의 개수 c  (0) 2024.11.17