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

1. 문제

11725번: 트리의 부모 찾기

2. 개요

정점 N개의 트리가 있고 N-1개의 간선 정보가 주어진다.

1이 루트 노드라고 할 때, 2번 노드부터 그 부모 노드의 번호를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 입력받은 간선 정보에 따라 그래프를 만들어 준다.

이때 뭐가 부모이고 뭐가 자식인지 모르기 때문에 양방향으로 만든다.

루트 노드부터 탐색을 시작한다. 만약 다음 탐색할 곳이 이미 방문한 곳이라면 넘어간다.

그렇지 않다면 다음 탐색할 곳의 부모를 현 위치로 갱신하고 방문 처리한다.

모든 노드를 탐색했다면 2번 노드부터 답을 출력한다.

3-2. Python

import sys
from collections import deque

N = int(sys.stdin.readline())

tree = [0 for i in range(N + 1)]
graph = [[] for i in range(N + 1)]
graph[0] = [1]

visited = [0 for i in range(N + 1)]

for i in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque([0])

while q:
    now = q.popleft()

    nxts = graph[now]

    for nxt in nxts:
        if visited[nxt]:
            continue

        visited[nxt] = 1
        tree[nxt] = now

        q.append(nxt)

for i in range(2, N + 1):
    print(tree[i])

3-3. C#

using System.Text;

namespace boj_11725
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int N = int.Parse(sr.ReadLine());

            List<List<int>> graph = new List<List<int>>();
            bool[] visited = new bool[N + 1];
            int[] tree = new int[N + 1];

            for (int i = 0; i < N + 1; i++)
            {
                graph.Add(new List<int>());
            }

            graph[0].Add(1);

            for (int i = 0; i < N - 1; i++)
            {
                string[] input = sr.ReadLine().Split();
                int a = int.Parse(input[0]);
                int b = int.Parse(input[1]);

                graph[a].Add(b);
                graph[b].Add(a);
            }

            Queue<int> queue = new Queue<int>();
            queue.Enqueue(0);

            while (queue.Count > 0)
            {
                int now = queue.Dequeue();
                List<int> nxts = graph[now];

                foreach (int next in nxts)
                {
                    if (visited[next])
                        continue;

                    visited[next] = true;
                    tree[next] = now;

                    queue.Enqueue(next);
                }
            }

            for (int i = 2; i < N + 1; i++)
                sw.WriteLine(tree[i]);

            sr.Close();
            sw.Close();
        }
    }
}