[Python] 백준, 1167(트리)

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

1167번: 트리의 지름

개요

어제 포스팅했던 트리의 지름과 똑같은 문항이다. input의 형식이 조금 바뀌어서 index와 관련해 생각할 부분이 늘어났지만 그 외의 풀이는 차이가 없다. 이전에 BFS로 문제를 해결했어서, 이번엔 DFS로 접근해봤는데 visit리스트의 리셋이나 변수들의 유효 범위 등 고려할 것들이 많아져 결국 포기. 추가로 우수 풀이 중 BFS/DFS가 아닌 괜찮은 접근의 풀이가 있어 소개하려 한다.

 

아이디어

- input 요소들은 리스트 형식으로 자료구조 정리

- global 함수를 이용해 변수들을 전역 변수로 지정

- visit 리스트로 방문하지 않은 노드들을 방문하며 가중치의 크기를 비교해 값 갱신

- 재귀를 이용해 dfs 함수 재호출

 

문제점

- 가중치가 가장 큰 노드를 찾은 이후 dfs를 재호출시, visit 리스트를 리셋해야 함

- 이미 global 함수로 지정된 변수들을 재정의해야 하는데 이 부분이 상당히 애매함

- 재귀로 dfs를 재호출 하기 위한 조건문의 위치가 애매함, 특정 노드만 살피는 게 아니라 모든 노드를 돌아보게 됨

 

 

# PYTHON CODE (1) - DFS

import sys

n = int(sys.stdin.readline())
tree = {j: [] for j in range(n + 1)}
visit = [False] * (n + 1)
cnt, now_node, last_dist = 0, 0, 0

for _ in range(n):
    list1 = list(map(int, sys.stdin.readline().split()))
    len_list1 = len(list1)
    x = list1[0]
    for i in range(1, len_list1 - 1, 2):
        tree[x].append([list1[i], list1[i + 1]])

def dfs(a):
    global cnt, now_node, last_dist
    visit[a] = True
    for k in tree[a]:
        next_node, now_dist = k[0], k[1]
        if not visit[next_node]:
            if last_dist <= now_dist:
                cnt += now_dist
                last_dist = now_dist
                now_node = next_node
            dfs(next_node)

dfs(1)

추가적으로, cnt나 now_dist, last_dist 등 변수 설정이 난잡하다. 어떤 방식으로 접근해서 정확히 어떤 값을 도출해내고자 하는지 조금 더 고민이 필요한 듯하다. 이 고민은 아래 풀이에서도 이어졌는데, 어제 이 문제를 풀면서 분명 완벽히 이해했다고 생각한 부분이 생각만큼 매끄럽지 않음을 느꼈다.

 

 

 

# PYTHON CODE (2) - BFS

import sys
from collections import deque

n = int(sys.stdin.readline())
tree = {j: [] for j in range(n + 1)}

for _ in range(n):
    list1 = list(map(int, sys.stdin.readline().split()))
    len_list1 = len(list1)
    x = list1[0]
    for i in range(1, len_list1 - 1, 2):
        tree[x].append([list1[i], list1[i + 1]])


def bfs(a):
    q = deque()
    q.append([a, 0])
    visit = [False] * (n + 1)
    visit[a] = True
    result = [0, 0]
    
    while q:
        now_node, cnt = q.popleft()  # cnt는 직전까지의 가중치의 합
        for j in tree[now_node]:
            next_node, next_dist = j[0], j[1]
            if not visit[next_node]:
                visit[next_node] = True
                q.append([next_node, cnt + next_dist])
                if result[1] <= cnt + next_dist:
                    result[0] = next_node
                    result[1] = cnt + next_dist

    return result

print(bfs(bfs(1)[0])[1])

 

 

# PYTHON CODE (3) - etc

import sys
from collections import deque

n = int(sys.stdin.readline())
tree = [[] for _ in range(n + 1)]

for _ in range(n):
    list1 = list(map(int, sys.stdin.readline().split()))
    x = len(list1)
    for i in range(1, x - 1, 2):
        tree[list1[0]].append([list1[i], list1[i + 1]])


def bfs(a):
    q = deque()
    q.append(a)
    visit = [0] * (n + 1)
    visit[a] = 1

    while q:
        node = q.popleft()
        for j in tree[node]:
            next_node, dist = j[0], j[1]
            if visit[next_node] == 0:
                q.append(next_node)
                visit[next_node] = visit[node] + dist

    return visit

visited = bfs(1)
result = bfs(visited.index(max(visited)))
print(max(result) - 1)

방문한 노드들의 가중치 합을 visit에 저장한다. (이때 방문 여부는 visit의 값이 0인지 아닌지에 따라 결정된다.) deque 에도 단순히 노드의 번호만이 추가되기 때문에 직관적이며, 마지막 처리는 visit의 값 중 가장 큰 값의 인덱스로부터 bfs 함수를 호출하며 마무리한다.