[C#] 백준 11725번 문제풀이

문제번호: 11725

문제명: 트리의 부모 찾기

문제링크: https://www.acmicpc.net/problem/11725

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

이번 문제는 방향이 주어지지 않은 오직 두 정점간의 관계만 주어진 트리 정보를 가지고 각 노드의 부모를 찾아내는 문제입니다. 인접 리스트 List<int>[]를 사용하여 각 노드의 관계를 저장하였고 DFS를 사용하여() 각 노드의 부모를 찾아내었습니다. 찾아낸 부모는 answer배열에 저장한 후 배열의 2번 인덱스부터 마지막까지 출력해주었습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    List<int>[] Adj = new List<int>[N]; // 1 ~ 7

    for (int i = 0; i < N; i++)
    {
        Adj[i] = new List<int>();
    }
    for (int i = 0; i < N - 1; i++)
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        Adj[input[0] - 1].Add(input[1]);
        Adj[input[1] - 1].Add(input[0]);
    }

    bool[] visited = new bool[N];
    int[] answers = new int[N];

    DFS(0);

    void DFS(int index)
    {
        visited[index] = true;
        foreach (int next in Adj[index])
        {
            int nextIdx = next - 1;

            if (!visited[nextIdx])
            {
                answers[nextIdx] = index + 1;
                // 부모 정보를 여기서 기록
                DFS(nextIdx);
            }
        }
    }

    for (int  i = 1;  i < answers.Length;  i++)
    {
        sw.WriteLine(answers[i]);
    }

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