[백준/Python] 13913 숨바꼭질 4

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

간단한 문제였지만 파이썬에서 사소한 오류로 반례를 찾는데 오랜 시간이 걸렸다.

다른 것이 아니라 While 문을 쓸때 매우 유의해야 한다는 점이었다.
보통 While 문을 쓸때는 종료조건이 0이 된다는 것을 상정하고 사용하기 마련이다. 자연스럽게 n 에서부터 -1 씩 감소한다면 문제가 없다.

하지만 이 문제에서는 종료조건이 0이 아니라 거꾸로 될 수가 있다.
트레이스에서는 종점에서 시점으로 거슬러 올라가게 되는데, 여기서 종점으로부터 시작하게 되면 종점이 0인 경우에 곧바로 문제가 발생하는 것이다. While 문 자체가 시작하지 않게 된다.

나는 실제로 종료 조건을 생각하고 코드를 작성하지 않았다. 더군다나 While문의 일반적인 종료 값인 0을 명시적으로 생각한 것도 아니었고, None 값이 나와도 종료되야 한다는 조건으로 작성이 되어버렸다. 따라서 이 부분을 아래처럼 수정해주었다.

• tree가 trace를 위한 자료 구조 일때,

path = []
while K:
    path.append(K)
    K = tree[K]

코드는 K가 None 이거나 0일때 멈춘다.
하지만 아래 처럼 변경해주어야 한다.

path = []
for _ in range(d):
    path.append(K)
    K = tree[K]