[Baekjoon] 1068 Python

1068번: 트리

 

예제는 4번째만 활용해서 작성하겠다.

예제 입력 4

9
-1 0 0 2 2 4 4 6 6
4

예제 출력 4

2

 

 

풀이과정

평소 풀이하던 방식으로 탐색하려다 보니 받은 데이터를 바탕으로 연결된 노드를 새로 생성해서 탐색했는데, 나중에 찾아보니 보다 간단한 방법이 있어서 같이 기록으로 남기려고 한다. 

1. 연결된 노드로 새로 생성한 후 탐색

1) 새로운 노드 선언 후 반복문을 돌리며 연결된 노드로 만들어 준다. 이때, 부모가 없는 경우는 -1이라는 전제와 예제 중에 -1이 없는 경우가 없길래 for문의 기준값을 1부터 시작해줬더니 오답처리가 되었다. 부모가 없는 경우가 있을 수 없는데 왜 틀리게 되는건지 모르겠다. 결국 0부터 돌려주어 해결했다. 

node = [[] for _ in range(N)]

for i in range(N):
    if n[i] != -1 and i != d:
        node[n[i]].append(i)

 아래 코드의 결과 담긴 노드는 다음과 같다.

[[1, 2], [], [3], [], [5, 6], [], [7, 8], [], []]

 

2) 삭제할 노드와 연결된 모든 노드를 지워주기 위한 dfs를 작성한다. 
4번째 노드와 연결되어 있는 5, 6노드를 방문하고, 6번째 노드와 연결된 7, 8을 방문하며 모두 pop하여 삭제하고 삭제처리한 노드는 False를 담아주어 구분할 수 있게 해준다. while문 다음에 node.pop(idx)와 같이 해당 노드를 리스트에서 아예 삭제해줘도 될 것 같다. 

def dfs(idx):
    while node[idx]:
        dfs(node[idx].pop())
    node[idx].append(False)

dfs를 실행한 후의 노드는 다음과 같아 진다.

[[1, 2], [], [3], [], [False], [False], [False], [False], [False]]

 

3) 최종적으로 dfs를 실행한 후, 반복문을 돌려 노드가 값을 가지고 있지 않은 경우만 찾아준다. 

dfs(d) # [[1, 2], [], [3], [], [False], [False], [False], [False], [False]]
for i in range(len(node)):
    if not node[i]:
        count += 1
print(count)

 

4) 전체 코드

import sys;

input = sys.stdin.readline

N = int(input())
n = list(map(int, input().split()))
d = int(input())

# 풀이 1. 연결된 노드로 새로 생성한 후 탐색
node = [[] for _ in range(N)]

for i in range(N):
    if n[i] != -1 and i != d:
        node[n[i]].append(i)


def dfs(idx):
    while node[idx]:
        dfs(node[idx].pop())
    node[idx].append(False)


count = 0
dfs(d)
for i in range(len(node)):
    if not node[i]:
        count += 1
print(count)

 

 

2. 기존에 받은 노드 내에서 탐색

1) 입력받은 정보 자체가 부모 노드의 값을 가지고 있기 때문에 처음부터 부모 노드 값을 활용해서 탐색할 수 있다. 
dfs안에서 N(노드개수)만큼 for문을 돌려 삭제할 노드를 가지고 있는 노드, 또 그 노드를 가지고 있는 노드, 이런식으로 탐색해준다. 

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

 

2) dfs탐색 후 삭제한 노드는 -2로 처리되었기 때문에 'n[i] != -2'라는 조건과 함께 부모노드를 가지고 있지 않은 'i not in n'을 기준으로 카운트 해준다. 

dfs2(d)
count = 0
for i in range(N):
    if n[i] != -2 and i not in n:
        count += 1

print(count)