문제 정보
[1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net](https://www.acmicpc.net/problem/1967)
문제
트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.
이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.
트리의 노드는 1부터 n까지 번호가 매겨져 있다.
입력
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
접근 방법
1.트리의 지름에 대해서 알아야 한다.
- 가중치가 없는 일반적인 트리의 지름 구하는 방법
- 순회 하면서 리프노드로 들어간다.
리프노드에서 리턴받은 현재 깊이 + 1을 리턴해준다
최상위 루트까지 다시 가서 최고값을 가지는게 트리으 지름이다. - 문제에서 트리의 지름을 구하는 방법
- 최상위 루트 노드 기준 으로 가장 멀리 떨어져 있는 노드 X 를 찾음
X 노드 기준 으로 가장 멀리 떨어져 있는 Y를 찾음
X-Y 거리가 트리의 가장 큰 지름이 됨
이걸 기준으로 문제를 풀고자 했다
2.리프노드 까지 들어가는 방법은 무엇이 있을까?
정확하게 제대로 이해하고 있지는 못하지만
재귀를 통해서 리프노드 까지 파고들어가는 방법에 대해서는 알고있다.
만만한 전위순회를 사용해서 리프노드 까지 들어가고
가중치(길이)를 더해주면서 길이가 가장 긴 위치의 노드번호를 찾자
3. 노드를 찾았는데???
여기서 문제가 막혔다.
전위순회를 했기 때문에 사실상 두번째 시작 노드는 리프노드
리프노드를 기준으로 전위순회를 하더라도 하단에 아무것도 없기 때문에 금방 끝나버린다.
스터디 코드리뷰, 솔루션을 본 후 생각한 풀이방법
4. 트리는 무향 그래프 이지만 유향 그래프처럼 표현된다.
트리를 꼭 트리처럼 만들어야 할까? 트리를 유향그래프로 만들어서 탐색해도 되는구나
bfs 도 괜찮고 dfs 도 괜찮을 거 같은데 트리는 아래로 파고드니까 dfs를 이용하자
풀이(DFS)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
def DFS(node_num, LEN):
# 그래프에 노드번호, 길이 순으로 저장돼 있음
for node, Len in graph[node_num]:
if res[node] == 0:
res[node] = Len + LEN
DFS(node, LEN + Len)
n = int(input())
graph = [[] for _ in range(n + 2)]
for _ in range(n - 1):
p, c, L = map(int, input().split())
graph[p].append([c, L])
graph[c].append([p, L])
# 루트 노드 기준으로 최장길이 노드를 찾는 첫번째 dfs 저장 배열
res = [0] * (n + 2)
res[1] = -1
DFS(1, 0)
# start_node = 루트에서 가장 길이가 먼 노드의 위치
start_node = res.index(max(res))
# start_node 기준으로 또 다시 거리를 찾기 위함
# 배열 초기화
res = [0] * (n + 2)
res[start_node] = -1
DFS(start_node, 0)
print(max(res))
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
def DFS(node_num, LEN):
# 그래프에 노드번호, 길이 순으로 저장돼 있음
for node, Len in graph[node_num]:
if res[node] == 0:
res[node] = Len + LEN
DFS(node, LEN + Len)
n = int(input())
graph = [[] for _ in range(n + 2)]
if n == 1:
print(0)
exit()
for _ in range(n - 1):
p, c, L = map(int, input().split())
graph[p].append([c, L])
graph[c].append([p, L])
# 루트 노드 기준으로 최장길이 노드를 찾는 첫번째 dfs 저장 배열
res = [0] * (n + 2)
res[1] = 1
DFS(1, 0)
# start_node = 루트에서 가장 길이가 먼 노드의 위치
start_node = res.index(max(res))
# start_node 기준으로 또 다시 거리를 찾기 위함
# 배열 초기화
res = [0] * (n + 2)
res[start_node] = 1
DFS(start_node, 0)
print(max(res))
계속해서 86프로쯤에 멈춰서 솔루션을 다시 보면서 했다.
생각하기에 중간에 틀리는 이유는 방문표시를 해주지 않았기 때문인 것 같았다.
또 100퍼센트에서 틀렸습니다가 나오기도 했는데 질문검색 게시판에서 정답을 찾았다.
처음에는 아래처럼 현재 방문위치를 1으로 바꾸어 주었는데
트리에 아무것도 없을때는 지름이 0 인데 미리 1으로 바꿨기 때문에 1이 출력돼서 틀린 것 같다.
if n == 1:
print(0)
exit()
를 적어서 억지로 종료해 주기도 했는데
max를 통해서 트리의 지름에 접근하기 때문에 현재 방문 노드에 대해 -1으로 초기화 해주면
0이 최대값이 되기 때문에 억지로 종료시켜주지 않아도 괜찮았다.
풀이(BFS)
import sys;
input = sys.stdin.readline
from collections import deque
def BFS(node, LEN):
global n, res
visited = [0] * (n + 1)
Q = deque()
visited[node] = 1
Q.append((node, LEN))
while Q:
now, now_dist = Q.popleft()
res.append((now, now_dist))
for node, dist in graph[now]:
if visited[node] == 0:
visited[node] = 1
Q.append((node, now_dist + dist))
n = int(input())
graph = [[] for _ in range(n + 2)]
for _ in range(n - 1):
p, c, L = map(int, input().split())
graph[p].append([c, L])
graph[c].append([p, L])
res = []
BFS(1, 0)
find = max(res, key=lambda x: x[1])
start_node = find[0]
res = []
BFS(start_node, 0)
find = max(res, key=lambda x: x[1])
print(find[1])
전형적인 BFS 코드로도 해결이 가능했다.
좀 어려웠던 점은 내 기준 (노드, 길이) 순으로 저장했고
함수를 돌며 res 리스트에 저장할때도 노드,길이 순으로 저장했기 때문에
그냥 max 를 쓰면 왼쪽 기준으로 최대값을 뽑아오게 된다
따라서 람다 함수를 이용해서 지름을 기준으로 최대값을 찾았고
인덱스를 통해서 시작노드와 최대지름을 찾아주었다.
느낀점
진짜 개어렵다...
트리 관련 문제를 3개 풀었는데 혼자서 제대로 푼게 단 한개밖에 없다.
트리가 고급 자료구조라고 하는데 공감하는 중
그래도 오랜시간 고민할 수 있는 버릇을 들이게 된 것 같다.
예전같으면 진작 포기하고 솔루션을 봤겠지만 어찌됐든 중간까지라도 혼자 해보고
도저히 모르겠는 상황에 솔루션을 봤다.(BFS는 가능하단걸 알고 혼자품!!! 내가이겼어)
여담이지만 이진탐색 트리는 완전 이진트리로는 구현하기는 했다
답이 완전 이진트리가 아니라서 그렇지...
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 10971 외판원 순회 2 (파이썬) (조합 생성방법) (0) | 2022.09.24 |
---|---|
백준 1182 부분수열의 합 (파이썬) (부분 집합 생성 방법) (0) | 2022.09.24 |
백준 1181 단어 정렬 (파이썬) (0) | 2022.09.20 |
백준 2589 보물섬 (파이썬) (0) | 2022.09.14 |
백준 1991 트리 순회 (파이썬) (0) | 2022.09.12 |