[알고리즘] 백준 11725 : 트리의 부모 찾기

문제 풀러 바로가기 >> 11725 : 트리의 부모 찾기

🗝️ 문제

---

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

입력

---

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

---

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

😒 내가 생각한 아이디어

---

👀 문제를 통해 이해해보기

트리의 아주 기초적인 구현 문제이다.
... 그치만 나는 자료구조들에 굉장히 약한 것 같다.
문제를 풀다 보면, 약한 부분들이 보이는데 전체적으로 구현/자료구조에서 큰 약점을 보이는 것 같다.

7
1 6
6 3
3 5
4 1
2 4
4 7

인풋으로 다음 값이 들어왔다고 쳐보자. 이 상황을 그림으로 표현한다면 다음과 같은 상황이다.

주어진 인풋값들이 부모-자식 순서의 관계로 주어진 게 아니라는 점을 유념해두어야 한다. 일례로 인풋값이 2 4로 주어졌음에도, 위의 그림에서는 4가 2의 부모임을 알 수 있다.
따라서 트리의 성질처럼 양방향(무방향) 그래프를 구현해주어야 한다.

그렇다면 0으로 초기화된 해당 노드들의 부모 노드를 담을 배열을 하나 선언하고, dfs를 돌며 전체 트리를 탐색하되, 해당 dfs 재귀호출 전에 현재 노드에 적힌 번호를 저장하면서 부모 노드 배열에 넣어준다. (parent[nxt] = cur이므로)

🖥️ 정답 코드

---

// 11725 트리의 부모 찾기
/*
  트리는 양방향 계층형 no사이클 구조이다.
  인접 리스트의 방식으로 트리를 구현한 후,
  부모 노드를 담을 배열을 하나 선언하면 된다.
*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int MAX = 100004;

void dfs(int cur, vector<int> adj[], vector<int> &parent){
  for(int nxt: adj[cur]) {
    if(parent[nxt] != 0) {
      continue;
    }
    parent[nxt] = cur;
    dfs(nxt, adj, parent);
  }
}
void print(vector<int> &parent, int &N){
  for(int i = 2; i <= N; i++){
    cout << parent[i] << "\n";
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  int N;
  vector<int> adj[MAX];
  vector<int> parent(MAX, 0); // 부모 노드를 담을 배열
  cin >> N;
  for(int i = 0; i < N-1; i++) {
    int x, y;
    cin >> x >> y;
    // 트리는 양방향(무방향) 그래프
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  dfs(1, adj, parent);
  print(parent, N);
}