문제 간략 설명: ‘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
[난이도]
[학습 개념]
[풀이]
그래프라는걸 이론만 알고 구현은 한 번도 해보지 않아 이 문제를 풀면서 공부할 의도로 선택했습니다.
처음 해보는 구현이다 보니 구글과 ai의 도움을 많이 받아 겨우겨우 해냈습니다. ᕦ(ò_óˇ)ᕤ
아무튼 처음 고민은 노드를 어떻게 표현(구현)할까입니다.
처음에는 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을 떠올리면서 해봤더니 이해가 더 쉬웠다.