[Condingame] DWARFS STANDING ON THE SHOULDERS OF GIANTSUTER(트리 자료구조의 높이 구하기 - 그래프, 재귀)

문제 간략 설명: ‘Dwarfs standing on the shoulders of giants'라는 말은 '거인의어깨 위에 있는 난쟁이가 거인보다 더 멀리 본다' 라는 옛 구절입니다. 아이작 뉴턴'saac Newton이 '내가 더 멀리 보았다면, 그것은 거인의어깨 위에 서 있었기 때문입니다'라고 인용하여 더 유명해진 말이기도 하죠. 새로운 발견은 그 이전에 있었던 여러 발견들의 토대 위에서 만들어진다는 얘기입니다.

[사진]

[Rules_규칙]

목표: 이전의 사람들의 영향력을 바탕으로 가장 긴 연쇄 영향력을 찾는 것입니다.

 

규칙:

• 각 사람은 서로 다른 정수로 나타낼 수 있습니다.
• A가 B에게 영향을 미치면, B가 A에게 영향을 미치지 않습니다.
• 여러 연쇄 영향력 중 가장 긴 것을 찾아야 합니다.

[문제]

 

https://www.codingame.com/training/medium/dwarfs-standing-on-the-shoulders-of-giants

Practice Memoization and Recursion with the exercise "Dwarfs standing on the shoulders of giants"

 

[난이도]

[학습 개념]

[풀이]

그래프라는걸 이론만 알고 구현은 한 번도 해보지 않아 이 문제를 풀면서 공부할 의도로 선택했습니다.

처음 해보는 구현이다 보니 구글과 ai의 도움을 많이 받아 겨우겨우 해냈습니다. ᕦ(ò_óˇ)ᕤ

 

아무튼 처음 고민은 노드를 어떻게 표현(구현)할까입니다.

처음에는 list를 생각해보았습니다.

list 연결 구조

하지만 노드는 자식 노드들과 단방향 연결되어 있어야 한다는 조건까지 있습니다.

list로는 노드가 자식 노들들을 2개 이상 못 가리킬거같아 고민해보았습니다.

그러다 결국 ai한테 물어보니 딕셔너리 클래스를 이용해서 key는 정수로 value를 List<int>로 하면 여러개의 자식 노드들을 가리킬 수 있다고 합니다.

그러면 이제 노드 구현은 끝났고 x에 y 값을 연결 시켜야 했습니다.

그래서

string[] inputs = Console.ReadLine().Split(' ');
            int x = int.Parse(inputs[0]);
            int y = int.Parse(inputs[1]);
            node.Add(x, y);

이렇게 바보같이 했다가 빨간줄한테 맞고 나서 딕셔너리의 두번째 인자가 List<int>이므로 객체 생성이 안됬다는걸 알고 부랴부랴 x값이 없을 때 빈 리스트 객체를 생성하게 코드를 짯습니다.

그 후 node[x].Add(y);로 정점 x에서 정점 y로 가는 간선 추가했습니다.

if (!node.ContainsKey(x))
                node.Add(x, new List<int>());

또는 이렇게 해도 됩니다.

if (!node.ContainsKey(x))
                node[x] = new List<int>();

.그 후 트리의 최대 깊이를 저장하는 변수 max를 선언하고, 루트 노드가 무엇인지 모르기 때문에 노드를 반복하면서 가장 깊은 트리 길이를 구합니다.

길이를 구하는 함수는 DFS_recursion으로 깊이 우선 탐색을 재귀적으로 스스로 반복하면서 매개변수로 노드의 값을 넣으면 연결된 노드를 찾고 없으면 0 있으면 현재 노드에 연결된 다른 정점들을 모두 탐색 하면서 max 값을 1 더합니다

[소스 코드]

 

using System;
using System.Collections.Generic;

class Solution
{
    // key가 정점, value가 해당 정점에서 진행 가능한 정점들의 목록인 Dictionary
    static Dictionary<int, List<int>> node = new Dictionary<int, List<int>>();

    // 해당 key에서 시작하여 가능한 루트를 찾아서 최대 깊이를 반환하는 함수
    static int DFS_recursion(int number)
    {
        int max = 0; // 현재 루트에서 탐색한 최대 깊이를 저장할 변수
        if (!node.ContainsKey(number) || node[number].Count == 0)
            // 현재 루트의 정점에 연결된 다른 정점이 없는 경우
            return 0;
        else
        {
            // 현재 루트의 정점에 연결된 다른 정점들을 모두 탐색
            foreach (int item in node[number])
            {
                int temp = DFS_recursion(item); // 현재 정점에서부터 시작하여 탐색한 최대 깊이를 구함
                if (max < temp)
                    max = temp; // 구한 최대 깊이가 현재까지 구한 최대 깊이보다 큰 경우, 최대 깊이를 갱신
            }
        }
        return max + 1; // 현재 루트를 포함한 최대 깊이를 반환
    }

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine()); // 정점 간의 관계 수
        for (int i = 0; i < n; i++)
        {
            // 두 사람 간의 관계를 입력받음 (x가 y를 영향을 미치는 관계)
            string[] inputs = Console.ReadLine().Split(' ');
            int x = int.Parse(inputs[0]);
            int y = int.Parse(inputs[1]);
            if (!node.ContainsKey(x))
                node[x] = new List<int>();
            node[x].Add(y); // 정점 x에서 정점 y로 가는 간선 추가
        }

        int max = 0; // 모든 루트에 대해 최대 깊이를 비교하여 가장 큰 값을 저장할 변수
        foreach (KeyValuePair<int, List<int>> item in node)// 루트 노드가 무엇인지 모르기 때문에 반복
        {
            int temp = DFS_recursion(item.Key); // 각 루트에 대해 최대 깊이를 계산
            if (max < temp)
                max = temp; // 계산한 최대 깊이가 현재까지 구한 최대 깊이보다 큰 경우, 최대 깊이를 갱신
        }

        // 최대 깊이 + 1 = 가장 긴 영향관계 연쇄에 참여한 사람 수
        Console.WriteLine(max + 1);
    }
}

 

[아쉬웠던 점]

어떻게 해야겠다는 생각은 있지만 코드를 어떻게 해야하는지 생각이 잘 안나 ai의 도움을 많이 받았습니다.

 

[새롭게 알게된 점]

1. node(정점)을 c#으로 구현할 때 딕셔너리 클래스의 두번째 인수로 List를 주면 된다는 걸 새롭게 알게 되었다.

2. 깊이,너비 우선 탐색 방법에 대해 이미지로 이해는 하고 있었지만 코드로 구현해 본 적은 없는데 이번에 해보면서     DFS (Depth-First Search), BFS (Breadth-First Search)에 대한 이해가 높아졌다.

3. 재귀 함수를 디버깅 하면서 stack을 떠올리면서 해봤더니 이해가 더 쉬웠다.