백준 18126 너구리 구구 (with Python)

어떤 문제?

제목에 적힌 문제 입니다 ^^

내가 작성한 Solution

트리의 개념을 이용해서 풀었습니다.

문제에서 생각해볼 점

• 문제에서 주어진 조건은 "노드가 N개 이고 간선이 N-1개로 이루어져 있다." 입니다. (아래 그림과 같이 표현할 수 있습니다.)

• 이 그림을 통해서 보여주고 싶은 내용은 다음과 같습니다: 순환하는 트리 구조는 나올 수 없다...! (2, 3, 4, 5 노드를 아무리 움직여봐도 순환 구조는 만들 수 없습니다.)

• 결국 조금만 생각해보면 Leaf node에 도착할 때마다 가장 큰 값을 갱신해주면 됩니다. (노드간의 거리는 모두 정수이므로, 가장 끝에 있는 노드들 중 하나의 node 가 무조건 입구로부터 가장 멀리 떨어져 있을 것입니다.)

• 그러면 leaf node 인것을 어떻게 알아낼 것인가?

  • 스택(DFS 활용)에 담긴 노드를 꺼낼때마다 방문 체크 를 해주면,

    • leaf node: 더이상 갈 수 있는 node 가 없습니다.

    • leaf node 를 제외한 다른 node: 갈 수 있는 node가 한 군데라도 있습니다.

코드 구현

N = int(input())

adj = [[] for _ in range(N+1)]

# 각 노드에서 갈 수 있는 노드를 모두 저장합니다.
for i in range(N-1):
    n1, n2, l = map(int, input().split())
    adj[n1].append([n2, l])
    adj[n2].append([n1, l])

visited = [0] * (N+1)

# 재귀 깊이 때문에 python 내에서 스택을 선언했습니다. 
# (시스템 스택 사용 X)
stack = [[1, 0]]

result = 0

while stack:
    v, l = stack.pop()
    visited[v] = 1
	
    # leaf node 인지 판별
    flag = False
    # 현재 v 노드가 갈 수 있는 곳이 한곳이라도 있다면 leaf 노드가 아닙니다.
    for tmpv, tmpl in adj[v]:
        if visited[tmpv] == 0:
            flag = True
	
    # leaf node가 아닌 경우, 스택에 저장합니다.
    if flag == True:
        if adj[v]:
            for nv, nl in adj[v]:
                if visited[nv] == 0:
                    stack.append([nv, l+nl])
    # leaf node인 경우, 최대값을 갱신해 줍니다.
    else:
        if l > result:
            result = l

print(result)