[Python] 백준 15900: 나무 탈출 (무방향 그래프, visited list)

문제 링크

15900번: 나무 탈출

문제 요약

node가 N개, vertex가 N-1개인 tree가 주어진다. 각 leaf에는 말이 있고, 한 턴에 한 번씩 움직여서 root에 도달하면 말을 제거하는데 이런 방식으로 움직일 말이 없어지는 사람이 패배하는 게임을 하고 있다. 주어지는 tree에서 게임을 할 때, 선공을 하는 형석이가 이긴다면 "Yes" 진다면 "No"를 출력하라.

풀이 설명

tree란 순환이 없는 그래프이다. 그중 특히 이진 트리는 leaf node를 제외한 나머지가 두 개씩 자식 노드를 가진 트리를 말하며, 위 문제에서는 그러한 조건이 달려있지 않았기 때문에 일반적인 트리로 가정한다.

 

문제를 풀 때, 일반적으로 문제에서 제시된 것들을 코드로 구현하고 거기에서 목표로 하는 값을 구하고자 하는 방식으로 접근하는 편인데, #트리 유형의 문제는 거의 처음 제대로 풀어보는 것이어서 처음에는 dictionary로 구현하려했다.

그런데, 이 문제가 트리 leaf의 depth를 구해야하는 문제이다보니, root로부터 dictionary를 만들 때에는 key를 부모 노드로 잡는 게 효율적인데 depth를 구할 때는 leaf로부터 올라오는 방법을 직관적으로 떠올리다보니 너무 비효율적인 아이디어였다.

 

컨디션도 안 좋아서 한참 고민하다가 결국 다른 분 코드를 참고하여 문제를 해결하였다. (감사합니다 🙇)

15900번: 나무 탈출

 

무방향 그래프(Undirected Graph)는 양방향 정보를 다 저장하는 것이 효율적일 수 있다.

위의 분은 각 linked라는 2차원 list로 정점간의 연결 관계를 node1 index에 append(node2), node2 index에 append(node1)의 방식으로 모두 저장하였는데 단방향 그래프(directed graph)가 아닌 경우에 이러한 방식이 추후 탐색할 때 훨씬 효과적이라고 생각하였다.

pop() 보다 visited list를 사용하는 것이 더 효율적인 경우가 많다.

또한 그래프 탐색 과정에서 이미 방문했던 노드에 대해 여러 번 depth를 측정하거나, 어떤 함수를 실행하는 경우 의도치않게 값이 중복하여 더해지거나 의미없이 같은 함수를 여러 번 실행하여 비효율적인 코드가 될 수 있다.

따라서, 이를 코드 차원에서 방지하여야하는데 이전 몇 문제에서 remove(O(N))와 같은 함수를 사용한 바 있었으나 이보다 remove나 pop(index)의 시간 복잡도가 O(N)이고 list[index]와 같은 인덱스 값 호출이 O(1)인 것만 비교하더라도 visited list를 사용하는 방식이 약간의 메모리 차이에도 훨씬 효율적이라는 것을 알 수 있었다.

 

적절한 목적에 맞는 자료 구조 선택과 데이터 저장 형태는 중요하다.
다른 사람들이 주로 사용하는 풀이 방식이 왜 주로 사용하게 되었는지 알게 되는 과정은 흥미진진하다 😈

 

전체 풀이 코드

import sys
sys.setrecursionlimit(500000)
input=sys.stdin.readline
N=int(input())
visited=[0 for _ in range(N+1)]
linked=[[] for _ in range(N+1)]
depth=[0 for _ in range(N+1)]

for i in range(N-1):
    node1, node2=map(int, input().split())
    linked[node1].append(node2)
    linked[node2].append(node1)

def depth_measure(start_node):
    visited[start_node]=1
    for end_node in linked[start_node]:
        if visited[end_node]==0:
            depth[end_node]=depth[start_node]+1
            depth_measure(end_node)
    
depth_measure(1)

total_depth=0
for i in range(2, N+1):
    if len(linked[i])==1:
        total_depth+=depth[i]


if total_depth%2==1:
    print("Yes")
elif total_depth%2==0:
    print("No")