백준 C# - 11725 +) 풀이

문제를 읽고 일단 그려봐야겠다는 생각이 들어서 그려보았다.

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

각 노드의 부모 노드 번호

그린 후 어느 알고리즘을 사용할까 하다가 DFS를 사용하기로 했다.

---

01 DFS 알고리즘

선택된 노드에서는 방문했다고 표시를 하고 부모노드를 기입하도록 하였다.

public static void DFS(int node)
{
    visited[node] = true;
    foreach (int neighbor in graph[node])
    {
        if (!visited[neighbor])
        {
            parent[neighbor] = node;
            DFS(neighbor);
        }
    }
}

---

02 그래프 생성

int N = int.Parse(Console.ReadLine());
graph = new List<int>[N + 1];
for (int i = 1; i <= N; i++)
{
    graph[i] = new List<int>();
}
parent = new int[N + 2];
visited = new bool[N + 2];
for (int i = 0; i < N - 1; i++)
{
    string[] input = Console.ReadLine().Split();
    int u = int.Parse(input[0]);
    int v = int.Parse(input[1]);
    graph[u].Add(v);
    graph[v].Add(u);
}

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace baek2
{
    class Program
    {
        static int[] parent;
        static bool[] visited;
        static List<int>[] graph;
        static StringBuilder sb = new StringBuilder();
        public static void DFS(int node)
        {
            visited[node] = true;
            foreach (int neighbor in graph[node])
            {
                if (!visited[neighbor])
                {
                    parent[neighbor] = node;
                    DFS(neighbor);
                }
            }
        }
        public static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            graph = new List<int>[N + 1];
            for (int i = 1; i <= N; i++)
            {
                graph[i] = new List<int>();
            }
            parent = new int[N + 2];
            visited = new bool[N + 2];
            for (int i = 0; i < N - 1; i++)
            {
                string[] input = Console.ReadLine().Split();
                int u = int.Parse(input[0]);
                int v = int.Parse(input[1]);
                graph[u].Add(v);
                graph[v].Add(u);
            }    
            DFS(1);

            for (int i = 2; i <= N; i++)
            {
                sb.AppendLine(parent[i].ToString());
            }
            Console.Write(sb.ToString());
        }
    }
}