[백준/파이썬] #22856

이전에 내가 풀었던 문제더라... 30분의 시간을 두고 풀어보았다. 예제 케이스는 다 맞췄는데 '틀렸습니다'가 떠서 예전 나의 풀이를 참고해보았다. 

 

우선은 30분 동안 시도해 본 풀이는 다음과 같다. 

import sys
from typing import List

sys.setrecursionlimit(10**9)


class Node:

    def __init__(self, value, parent, left_child, right_child):
        self.value: int = value
        self.parent: Node | None = parent
        self.left_child: Node | None = left_child
        self.right_child: Node | None = right_child
        self.visited: bool = False


def semi_inorder_search(current_node: Node | None):
    global count, visited_count
    if visited_count >= N:
        return
    if not current_node:
        return
    if current_node and not current_node.visited:
        current_node.visited = True
        visited_count += 1
    count += 1
    if current_node.left_child and not current_node.left_child.visited:
        semi_inorder_search(current_node.left_child)
    if current_node.right_child and not current_node.right_child.visited:
        semi_inorder_search(current_node.right_child)
    if current_node.parent:
        semi_inorder_search(current_node.parent)


N = int(input())
count = 0
visited_count = 0
nodes: List[Node | None] = [None] * (N+1)

for _ in range(N):
    current, left, right = map(int, input().split())
    if not nodes[current]:
        nodes[current] = Node(value=current, parent=None, left_child=None, right_child=None)
    if left != -1:
        nodes[left] = Node(value=left, parent=nodes[current], left_child=None, right_child=None)
        nodes[current].left_child = nodes[left]
    if right != -1:
        nodes[right] = Node(value=right, parent=nodes[current], left_child=None, right_child=None)
        nodes[current].right_child = nodes[right]


semi_inorder_search(nodes[1])
print(count-1)

 

풀이를 참고해서 풀어봤다. 

import sys

sys.setrecursionlimit(10**9)
N = int(input())
tree = {}

def dfs_all(node: int):
    global count_all
    visited[node] = True

    if not visited[tree[node][0]] and tree[node][0] != -1:
        dfs_all(tree[node][0])
        count_all += 1
    if not visited[tree[node][1]] and tree[node][1] != -1:
        dfs_all(tree[node][1])
        count_all += 1


def dfs_right(node: int):
    global count_right
    visited[node] = True

    if not visited[tree[node][1]] and tree[node][1] != -1:
        dfs_right(tree[node][1])
        count_right += 1


for _ in range(N):
    current, left, right = map(int, input().split())
    tree[current] = [left, right]

count_all = 0
visited = [False] * (N+1)
dfs_all(1)
count_right = 0
visited = [False] * (N+1)
dfs_right(1)
print(2*count_all - count_right)

 

처음에는 왜 '전체 이동하고 왕복했을 때 지나간 간선 개수 - 오른쪽으로만 이동했을 때 끝까지 간 편도 간선 개수'를 하면 정답이 나오는지 이해가 잘 안 되어서 GPT에게도 물어봤다.

 

이해한 바는 다음과 같다.

 

dfs_all()로 계산된 count_all에 2를 곱하면 '중위 순회를 거쳐서 루트 노드까지 돌아올 때까지 거친 간선 수'가 된다. 그런데 문제에서는 '마지막 노드'에 도달하면 멈춰야 한다. 

 

그래서 count_all * 2의 값에서 '루트 노드에서 맨 마지막 노드까지 갈 때 거친 간선 수(dfs_right으로 계산된 count_right)를 빼 줘야 하는 것이다.