[백준 11725] 트리의 부모 찾기 (C#, C++) - soo:bak

문제 링크

11725번 - 트리의 부모 찾기

설명

N개의 노드로 이루어진 트리가 주어지는 상황에서, N (2 ≤ N ≤ 100,000)과 트리를 구성하는 간선 정보가 주어질 때, 루트를 1번 노드로 정했을 때 각 노드의 부모를 구하는 문제입니다.

트리는 N개의 노드와 N-1개의 간선으로 이루어져 있으며, 루트가 정해지지 않은 상태로 주어집니다.

접근법

루트 1번에서 DFS를 수행하여 각 노드의 부모를 찾습니다.

먼저 입력으로 주어진 간선 정보를 인접 리스트로 저장합니다. 트리는 무방향 그래프이므로 양쪽 방향으로 모두 연결합니다.

루트 1번부터 DFS를 시작하여 인접한 노드를 탐색합니다. 방문하지 않은 인접 노드를 발견하면 그 노드의 부모를 현재 노드로 기록하고, 재귀적으로 탐색을 이어갑니다.

이렇게 모든 노드를 방문하면 각 노드의 부모 정보가 완성되므로, 2번 노드부터 N번 노드까지 부모를 출력합니다.

시간 복잡도는 O(N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace Solution {
  class Program {
    static List<int>[] adj;
    static int[] parent;
    static bool[] visited;

    static void Dfs(int cur) {
      visited[cur] = true;
      foreach (var nxt in adj[cur]) {
        if (visited[nxt])
          continue;
        parent[nxt] = cur;
        Dfs(nxt);
      }
    }

    static void Main(string[] args) {
      using var sr = new StreamReader(Console.OpenStandardInput());
      using var sw = new StreamWriter(Console.OpenStandardOutput());

      var n = int.Parse(sr.ReadLine()!);
      adj = new List<int>[n + 1];
      for (var i = 1; i <= n; i++)
        adj[i] = new List<int>();
      parent = new int[n + 1];
      visited = new bool[n + 1];

      for (var i = 0; i < n - 1; i++) {
        var parts = sr.ReadLine()!.Split();
        var u = int.Parse(parts[0]);
        var v = int.Parse(parts[1]);
        adj[u].Add(v);
        adj[v].Add(u);
      }

      Dfs(1);

      for (var i = 2; i <= n; i++)
        sw.WriteLine(parent[i]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

vvi adj;
vi parent;
vb visited;

void dfs(int cur) {
  visited[cur] = true;
  for (int nxt : adj[cur]) {
    if (visited[nxt])
      continue;
    parent[nxt] = cur;
    dfs(nxt);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  adj.assign(n + 1, {});
  parent.assign(n + 1, 0);
  visited.assign(n + 1, false);

  for (int i = 0; i < n - 1; i++) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfs(1);

  for (int i = 2; i <= n; i++)
    cout << parent[i] << "\n";

  return 0;
}