[BOJ][python] 1068. 트리

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

1068번: 트리

---

💡IDEA

트리, DFS를 사용하는 문제이다.

처음엔 큐를 사용하여 삭제한 노드에 연결된 모든 노드들을 -1로 갱신하여 지워주는 방법으로 풀었으나 99%에서 실패가 떴다. 찾아보니 0번 노드만 남은 경우에도 결과값이 1이여야 하는데, 0으로 출력되고 있었다. 이것을 해결하기 위해 여러 방법으로 수정했으나 도무지 알 수가 없어서 DFS를 사용했다.

삭제한 노드에 연결된 모든 노드들의 부모 노드를 -2로 갱신하는 DFS함수(solve)를 구현하고, i번 노드의 부모 노드가 -2가 아니면서 i 값이 부모 노드 배열에 없는 경우에만 개수를 카운트했다.

이렇게 하니 0번 노드는 부모 노드로 -1을 가지고 있어서 -2를 가지고 있는 노드들과 달라지기 때문에 0번 노드만 남은 겨웅에 결과값이 0으로 올바르게 출력된다.

# 특수 케이스 예시 입력
-2
-1 0
1

# 특수 케이스 예시 출력
1

 

📌CODE

# 99% 실패 코드
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
parent = list(map(int, input().split()))
rem = int(input())

def solve(n):
    q = deque([n])
    parent[n] = -1
    while q:
        cn = q.popleft()
        for i in range(N):
            if parent[i] == cn:
                q.append(i)
                parent[i] = -1

solve(rem)

cnt = 0
for i in range(N):
    if parent[i] == -1:
        continue
    if i not in parent:
        cnt += 1
print(cnt)

# 성공 코드
import sys
input = sys.stdin.readline

N = int(input())
parent = list(map(int, input().split()))
rem = int(input())

def solve(n):
    parent[n] = -2
    for i in range(N):
        if n == parent[i]:
            solve(i)

solve(rem)

cnt = 0
for i in range(N):
    if parent[i] != -2 and i not in parent:
        cnt += 1
print(cnt)