[BOJ 1068 파이썬] 파이썬 트리 BFS 풀이

 

1068번: 트리

 

이 문제를 처음 보자마자 든 생각은 BFS로 풀면 되지 않을까? 였다.

 

먼저, 지워질 노드를 고려하지 않고 모든 노드들을 edge로 연결해주어 그래프를 만들어주었다.

 

이후, BFS로 탐색 하되 삭제한 노드로는 탐색하지 않게끔 예외를 주고, 부모노드가 삭제되었을 때의 예외를 해주었다.

루트노드는 연결 edge가 하나 밖에 없으므로 탐색시 연결 edge가 하나라면 답에 더해주었다.

 

그래서 처음 완성한 코드가

 

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())

temp = list(map(int,sys.stdin.readline().rstrip().split()))

## 삭제될 노드
remove = int(sys.stdin.readline().rstrip())

##그래프
graph = [[] for i in range(N)]

##BFS탐색을 위한 배열
visited = [False for _ in range(N)]

parent_node = 0

##그래프 생성 및 edge 연결
for i in range(N):
    if temp[i] != -1:
        graph[i].append(temp[i])
        graph[temp[i]].append(i)
    else:
        ##부모노드부터 탐색을 시작해야하므로 부모노드의 번호 저장
        parent_node = i

answer = 0

##BFS
def bfs(p):
    global answer
    q = deque()
    q.append(p)
    visited[p] = True

    while len(q) != 0:
        now = q.popleft()
        ##그래프에 연결 되어있는 곳들을 바로 탐색
        for link in graph[now]:
            ##연결 되어있는 곳이 삭제된 노드가 아니고, 이미 방문된 노드라면?
            if link != remove and not visited[link]:
                q.append(link)
                visited[link] = True
             
        ##연결된 노드가 하나이고, 부모노드가 아니라면,
        if (len(graph[now]) == 1 and now != parent_node):
            answer += 1

##부모노드를 삭제하지 않았다면,
if remove != parent_node:
    bfs(parent_node)



print(answer)

 

 

인데, 계속 70~80퍼센트 사이에서 틀렸다고 나왔다.

 

예외를 빠트린게 있었는데,

다음과 같은 경우였다.

 

다음과 같이 노드가 삭제될때, 2번 노드는 연결된 edge가 2개임에도 불구하고, 리프노드로 처리되지 않았다.

그래서 이 부분을 해결해주고 완성된 코드가,

 

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())

temp = list(map(int,sys.stdin.readline().rstrip().split()))

## 삭제될 노드
remove = int(sys.stdin.readline().rstrip())

##그래프
graph = [[] for i in range(N)]

##BFS탐색을 위한 배열
visited = [False for _ in range(N)]

parent_node = 0

##그래프 생성 및 edge 연결
for i in range(N):
    if temp[i] != -1:
        graph[i].append(temp[i])
        graph[temp[i]].append(i)
    else:
        ##부모노드부터 탐색을 시작해야하므로 부모노드의 번호 저장
        parent_node = i

answer = 0

##BFS
def bfs(p):
    global answer
    q = deque()
    q.append(p)
    visited[p] = True

    while len(q) != 0:
        now = q.popleft()
        ##그래프에 연결 되어있는 곳들을 바로 탐색
        for link in graph[now]:
            ##연결 되어있는 곳이 삭제된 노드가 아니고, 이미 방문된 노드라면?
            if link != remove and not visited[link]:
                q.append(link)
                visited[link] = True
             
            if link == remove:
                ##연결되어있는 곳이 삭제된 노드인데, 지금 노드의 edge가 2개이고, 부모노드가 아니라면
                if len(graph[now]) == 2 and now != parent_node:
                    answer+=1
                ##연결되어있는 곳이 삭제된 노드인데, 지금 노드의 edge가 한개이고, 이것이 부모노드라면
                if len(graph[now]) == 1 and now == parent_node:
                    answer+=1
        ##연결된 노드가 하나이고, 부모노드가 아니라면,
        if (len(graph[now]) == 1 and now != parent_node):
            answer += 1

##부모노드를 삭제하지 않았다면,
if remove != parent_node:
    bfs(parent_node)



print(answer)

 

탐색 시 삭제될 노드로 이어져있는데, 

지금 노드의 edge가 2개이며 루트노드가 아니라면, 해당 노드가 리프노드라고 판단하고

지금 노드의 edge가 하나이고 루트노드라면, 해당 노드는 루트노드이지만 리프노드가 되므로 리프노드라고 판단해주었다.

 

결과 성공!

 

 

트리문제긴 했지만, BFS 연습겸 구현 연습으로 매우 좋은 문제였다고 생각한다.

이런 예외처리는 항상 필수이니,,😅

 

풀이에 다른 의견이 있으시다면 댓글 남겨주세요!!