[백준][C#] 1967 트리의 지름 - 골드4

문제 보기

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

문제                           

 

입력                          

 

출력                          

 

 

시간 제한	메모리 제한
2 초	128 MB

 

풀이방법                 

이 문제는 트리 문제로 보이지만 사실 딱히 트리로 풀 필요는 없다.

 

나는 인접 리스트와 DFS를 통해 정답을 맞추었으며

시간초과가 날까 조금 걱정하였으나... 깔끔하게 성공하였다.

1초짜리 문제였다면 다른 방식으로 풀어야할지도...

 

골드4문제 답지않게 매우 쉬운 풀이법(그리고 높은 정답 비율)을 가지고 있다.

그냥 트리가 아닌 무방향 그래프라 생각하고 풀어보자!

 

            List<(int node, int distance)>[] trees = new List<(int, int)>[n + 1];
            for(int i = 1; i <= n; i++)
            {
                trees[i] = new List<(int node, int distance)>();
            }

            for (int i = 1; i < n; i++)
            {
                string[] inputs = reader.ReadLine().Split();

                trees[int.Parse(inputs[0])].Add((int.Parse(inputs[1]), int.Parse(inputs[2])));
                trees[int.Parse(inputs[1])].Add((int.Parse(inputs[0]), int.Parse(inputs[2])));
            }

 

노드 번호와 가중치를 가진 인접 리스트를 만들어 노드를 연결해준다.

무방향 그래프이기 때문에 서로 추가해 주어야 한다.

 

            int max = 0;
            // 모든 노드를 순회하며 깊이 우선 탐색을 진행한다.
            for (int i = 1; i <= n; i++)
            {
                bool[] visited = new bool[n + 1];
                DFS(visited, i, 0);
            }

            void DFS(bool[] visited, int node, int sum)
            {
                if (!visited[node])
                {
                	// 한 노드에서 다른 노드에 도착하였다면
                    // 길이와 max값을 비교하여 갱신.
                    max = Math.Max(max, sum);
                    visited[node] = true;

                    int count = trees[node].Count;
                    for(int i = 0; i < count; i++)
                    {
                    	// 지금까지의 길이에, 다음 노드까지 가중치를 추가.
                        DFS(visited, trees[node][i].node, sum + trees[node][i].distance);
                    }
                }
            }

 

1부터 n번까지 모두 한 번씩 스타트 노드로 지정해준다 생각하면 된다.

가중치를 계속 더해주고 새 노드에 도착할 때마다 최대 지름 값을 갱신해주기.

 

 

 

 

전체 코드 보러가기

https://github.com/MetroDefro/BackjoonCodingTest/tree/main/%EB%B0%B1%EC%A4%80/Gold/1967.%E2%80%85%ED%8A%B8%EB%A6%AC%EC%9D%98%E2%80%85%EC%A7%80%EB%A6%84

 

 

백준 깃허브 연동 https://mountain-noroo.tistory.com/38