[Baekjoon] 11725 - 트리의 부모 찾기

1. 문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

2. 분석 및 아이디어

이 문제에서 까다로웠던 점은 트리에서 연결된 간선이 주어질 때 무방향으로 주어진다는 점이다. (누가 부모인지 알 수 없음)

그래서 필자는 트리를 루트부터 시작해 dfs로 탐색하면서 부모->자식 노드 연결을 끊어 주는 방식을 생각했다.

 

처음에는 인접 행렬 방식으로 무식하게 구현했는데, 이러면 답은 구할 수 있지만 메모리 초과가 난다.

 

그래서 queue나 deque, list, map을 이용한 인접 리스트 방식으로 구현을 시도했는데, map, deque, queue는 인덱싱이 되지 않거나, 중간에서 요소 삭제가 안된다는 단점이 있었고, 

 

list는 인덱싱이 안될 뿐더러, 중간에 요소를 삭제하면 for문으로 모든 요소를 확인하는 중에 반복 횟수가 달라진다는 치명적인 단점이 존재했다.

 

그래서 결국 vector형의 이중 배열로 구현을 했고, 연결을 끊은 노드는 노드의 번호 대신 -1로 표시해 부모 노드의 번호가 0번 이상인 것만 출력하도록 해 문제를 해결했다.

 

3. 소스코드

// Baekjoon No. 11725 트리의 부모 찾기 - 220923~220924
// Time Complexity O(n)
// #tree traversal, dfs

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

void disconnect(vector<vector<int>>& node, vector<int>& visited, int n,  int nodeIdx);   // 해당 nodeIdx에 연결된 부모->자식 연결 끊어줌
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, child, parent;
    int i, j;
    cin >> n;
    vector<vector<int>>node(n);
    // map<int, vector<int>> node;
    vector<int> visited(n, 0);
    for (i = 0; i < n - 1; i++) {
        cin >> child >> parent;
        // 일단 부모->자식 자식->부모 모두 연결
        child--;
        parent--;
        
        node[child].push_back(parent);
        node[parent].push_back(child);
    }

    // solving
    /** 알고리즘 구상
    * 1) 노드 입력, 간선 양방향 연결
    * 2) 노드 1부터 DFS 진행하며 부모->자식 연결 끊어줌
    * 3) 결과 출력
    */
    disconnect(node, visited, n, 0);

    // output
    for (i = 1; i < n; i++) {
        for (j = 0; j < node[i].size(); j++) {
            if (node[i][j] >= 0) {
                cout << node[i][j] + 1<<"\n";
            }
            
        }
    }
    return 0;
}

void disconnect(vector<vector<int>>& node, vector<int>& visited, int n, int nodeIdx) {
    int i, size = node[nodeIdx].size(), nextIdx;
    // mark visited
    visited[nodeIdx] = 1;
    // finds if there is child node, and disconnects the connection
    // go to child node, and continues process
    for (i = 0; i < size; i++) {
        if (!visited[node[nodeIdx][i]] && node[nodeIdx][i] > 0) {
            nextIdx = node[nodeIdx][i];
            node[nodeIdx][i] = -1;
            disconnect(node, visited, n, nextIdx);
        }
    }
    return;
}

 

4. 개선할 점

다른 분의 코드를 참고하니, bfs를 이용해 차례대로 노드를 탐색하면서, 자신 다음의 노드가 방문되지 않았다면

부모 노드만을 저장하는 n - 1길이의 배열을 만들어

자신 다음 노드의 부모로 현재 노드를 저장하는 코드를 봤다.

 

dfs를 구현한다고 vector 이중배열로 삽입, 수정한 내 코드보다 간결해 보였다.

부모 노드라는 특성과 관련 있는 탐색은 bfs이므로 이를 이용해볼 생각을 하면 좋았을 것 같다.