[백준 1068] 파이썬 - 트리

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

1068번: 트리

 

# 조건

- 트리에서 리프노드란, 자식의 개수가 0인 노드
- 트리가 주어질 때, 노드 하나를 지울 것인데, 그 때 남은 트리에서 리프 노드의 개수를 구하여라

 

 

# 접근 방법

- 노드 하나를 지웠다면 아래 자식 노드들 또한 함께 지워지는 것이 규칙
- 따라서 지워지는 노드 기준, 아래로 연결되어 있는 노드들을 -2로 변경해준다.
-  -2인 경우는 나올 수 없는 수 이기도 하며 False로 설정해주니 제일 부모노드 0번이 남는 경우 0==False가 되어 오답이 되었다.

 

# 처음 푼 코드


import sys  
sys.stdin = open('input.txt')  
  
# N = 노드의 개수  
# 각 노드의 부모가 주어지는데 -1인 경우 부모가 없다.  
# 세 번째 줄에는 지울 노드의 번호  
  
def leaf(erase):  
    # 방문 리스트  
    visited = [False] * N  
  
    # 리스트 내에 부모노드의 번호들을 True로 변경시켜준다.  
    for i in node:  
        if i > -1 and i in node:  
            visited[i] = True  
    # 지우는 번호의 부모노드 길이가 1이라면 False로 바꿔주기  
    # 안해줬을 때의 예시 0과 1만 있을 때 1을 삭제시 0이 출력  
    if node.count(node[erase]) < 2:  
        visited[node[erase]] = False  
    # 지우는 노드에서 시작  
    stack = [erase]  
    # 방문 기록 남겨준다.  
    visited[erase] = True  
  
    while stack:  
        start = stack.pop()  
        for i in range(len(node)):  
            # 지우는 부분의 자식 노드를 true로 변경해준 후 주소에 담아준다.  
            if node[i] == start:  
                visited[i] = True  
                stack.append(i)  
  
    return visited  
  
N = int(input())  
node = list(map(int, input().split()))  
erase = int(input())  
a = leaf(erase).count(False)  
print(a)

• 처음 푼 코드의 경우 오답은 아니지만 코드가 되게 길어 주석이 없다면 가독성이 좋지 않았다.
• 방문 리스트를 만들어 준 후 기록을 남겨주었는데 한 번 지나간 노드는 전체 결과에 영향을 주지 않는다는 것을 알게 되었다.

 

# 불필요한 부분 수정 후 코드

def leaf(erase):  
    # 방문 리스트  
    stack = [erase]  
    # 방문 기록 남겨준다.  
    # False로 할경우 0 노드만 남은 경우 틀리게된다 0 == False
    node[erase] = -2  
    while stack:  
        start = stack.pop()  
        for i in range(len(node)):  
            # 지우는 부분의 자식 노드를-2로 변경해준다.  
            if node[i] == start:  
                node[i] = -2  
                stack.append(i)  
  

  
N = int(input())  
node = list(map(int, input().split()))  
erase = int(input())  
leaf(erase)  
a= 0  
for i in range(N):  
    if node[i] != -2 and not i in node:  
        a +=1  
print(a)

=====================================================================
# 재귀 이용
def leaf(erase):  
    node[erase] = -2  
    for i in range(len(node)):  
        # 지우는 부분의 자식 노드를 true로 변경해준 후 주소에 담아준다.  
        if node[i] == erase:  
            leaf(i)  
  
N = int(input())  
node = list(map(int, input().split()))  
erase = int(input())  
leaf(erase)  
  
a =0  
for i in range(len(node)):  
    if node[i] != -2 and not i in node:  
        a +=1  
print(a)

• 접근방법에 나와있는 것처럼 node 리스트 원본에 직접 기록을 남겨주니 코드는 짧아졌지만, 재사용이 필요한 문제인 경우 처음과 같은 방법이 좋아보인다. 
• 아래는 똑같은 방식이지만 재귀로 풀어주니 훨씬 보기 좋았다!