[Python/파이썬] 백준 14675번 단절점과 단절선

14675번: 단절점과 단절선

문제

그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다.

• 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다.
• 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다.

이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다.

• 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프

트리의 정보와 질의가 주어질 때, 질의에 대한 답을 하시오.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정보 a, b가 주어진다. 이는 a정점과 b정점이 연결되어 있다는 뜻이며, 입력으로 주어지는 정보는 트리임이 보장된다. (1 ≤ a, b ≤ N)

다음 줄에는 질의의 개수 q가 주어진다. (1 ≤ q ≤ 100,000) 다음 q줄에는 질의 t k가 주어진다. (1 ≤ t ≤ 2) t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다. t가 1일 때는 (1 ≤ k ≤ n)이며, t가 2일 때는 (1 ≤ k ≤ n - 1)이다. 

출력

프로그램의 출력은 표준 출력으로 한다. q줄에 대하여 해당 질의에 대한 답을 한다. 각각은 개행으로 구분하며, 질의가 맞다면 ‘yes’를, 질의가 틀리면 ‘no’를 출력한다. 

코드

• 시간 초과 발생한 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())    # 트리의 정점의 개수
tree = [[] for _ in range(n+1)] # 트리
bridge = []   # k번째 입력 간선

for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    bridge.append((a,b))

def bfs(node):
    search_node_num = 1 # 방문한 노드 개수
    
    q = deque([node])
    visited = [False] * (n+1)
    visited[node] = True    # 처음 노드 방문처리
    
    while q:
        now = q.popleft()
        for nx in tree[now]:
            if not visited[nx]:
                q.append(nx)
                visited[nx] = True
                search_node_num +=1
    return search_node_num
    
for _ in range(int(input())):   # 질의
    # t == 1 : k번 정점이 단절점인지? (1 <= k <= n)
    # t == 2 : k번째 간선이 단절선인지? (1 <= k <= n-1)
    t, k = map(int, input().split())    
    if t == 1:
        flag = False
        tmp = tree[k]
        tree[k] = []
        for node in tmp:
            tree[node].remove(k)
        for node in tmp:
            if bfs(node) == n - 1:  # 그 노드만 없어지고 2개로 쪼개지지는 않음
                flag = True
                break
        tree[k] = tmp
        for node in tmp:
            tree[node].append(k)
        print("no" if flag else "yes")
    else:
        a, b = bridge[k-1]
        tree[a].remove(b)
        tree[b].remove(a)
        if bfs(a) == n: # 간선 제거해도 다 연결되어 있는 경우
            print("no")
        else:           # 간선 제거하면 쪼개지는 경우
            print("yes")
        tree[a].append(b)
        tree[b].append(a)

위 풀이는 시간 초과

• tree: 간선들의 연결 정보 저장하는 배열
• bridge : k번째 입력된 간선 정보 저장하는 배열

1. k번째 정점이 단절점인지? ⇒ k번 정점에 연결된 서브트리에 대해 bfs()를 돌면서 서브트리의 노드 개수를 세서 서브트리의 노드 개수가 n-1이라면 k번 정점만 제거되고 나머지는 모두 연결되어 있으므로 “yes”를 출력. 그게 아니라면 “no”를 출력
2. k번째 간선이 단절선인지? ⇒ k번째 간선의 정보를 tree 배열에서 모두 지우고 bfs()를 돌려서 트리의 노드의 개수를 센다. 노드의 개수가 n이라면 k번째 간선을 제거해도 아직 트리가 모두 연결이 되어있는 것이므로 “no”를 출력. 그게 아니라면 “yes”를 출력.

 

• 정답 코드

import sys
input = sys.stdin.readline

n = int(input())    # 트리의 정점의 개수
tree = [[] for _ in range(n+1)] # 트리

for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for _ in range(int(input())):   # 질의
    t, k = map(int, input().split())    
    if t == 1:  # k번 정점이 단절점인지? (1 <= k <= n)
        if len(tree[k]) == 1:   # k번 노드가 리프노드인 경우 => 단절점 X
            print("no")
        else:
            print("yes")
    else:       # k번째 간선이 단절선인지? (1 <= k <= n-1)
        print("yes")

1.  

트리의 특성을 생각해보면 쉽게 풀 수 있는 문제.

트리는 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프이다.

1. k번째 정점이 단절점이냐?
   ⇒ 트리의 모든 자식 노드는 단 하나의 부모 노드만을 갖는다. 따라서 부모 노드가 제거 되면 트리는 2개로 쪼개질 수 밖에 없다. 정점을 제거했는데 트리가 나누어지지 않는 경우는 본인이 리프 노드인 경우이다. tree[k]의 길이를 확인하여 길이가 1이라면 부모 노드와의 간선만을 갖는 리프 노드이므로 이 경우에만 “no”를 출력해주고 나머지는 “yes”를 출력해주면 된다.
2. k번째 간선이 단절선이냐?
   ⇒ 트리는 N개의 노드가 있을 때 N-1개의 간선을 갖는다. 따라서 어떠한 간선을 제거하더라도 트리는 2개로 나누어진다. 그래서 이 질의는 무조건 “yes”를 출력하게 된다.