BOJ11266 단절점

문제

BOJ11266 단절점
플래티넘V | 백준 11266 | Python3 파이썬 풀이

알고리즘

단절점, 단절선에 대한 알고리즘은 단절점(Articulation Point)와 단절선(Bridge) 글을 참고하였다.

여기서 중요한 포인트는 DFS 탐색을 하며 각 노드에 번호를 붙였을 때, 특정 노드 X와 연결된 노드 중 X보다 늦게 탐색되는 노드들에서 X 노드보다 먼저 탐색되는 노드로 가는 경로가 존재하지 않는다면 X 노드는 단절점이 된다는 것이다.

만약 X 노드가 루트 노드일 때는 예외처리를 해주어야 한다. 루트인 노드는 자식이 2개 이상이면 반드시 단절점이 된다.

코드

import sys
from collections import deque
sys.setrecursionlimit(10**4)

input = sys.stdin.readline


def DFS(curr : int, isroot : bool) -> int:
    global nodecnt, discover
	
    # 노드 번호를 부여
    nodecnt += 1
    discover[curr] = nodecnt
	
    # 현재 노드의 값
    ret = discover[curr]
    child = 0
	
    # 인접 노드
    for next in adjlist[curr]:
    	# 자식 중 번호를 붙이지 않은 노드가 있다면
        if discover[next] == 0:
            child += 1

            # 자식 중 최소 번호를 찾아냄
            mindisc = DFS(next, 0)

            # 만약 DFS를 통해 찾아낸 최소 번호가 이 노드보다 크다면
            if not isroot and mindisc >= discover[curr]:
            	# 이 노드가 단절점이 된다
                cut[curr] = 1
			
            # 최소 번호 저장
            ret = min(ret, mindisc)
        
        else:
            ret = min(ret, discover[next])

    # 루트 노드일 때 자식이 2개 이상이라면 단절점이다.
    if isroot and child > 1:
        cut[curr] = 1
    
    return ret


V, E = map(int, input().split())

adjlist = [[] for _ in range(V + 1)] # 인접 리스트
discover = [0 for _ in range(V + 1)] # 노드 번호
cut = [0 for _ in range(V + 1)] # 단절점 여부
nodecnt = 0 # 노드에 번호를 붙이기 위한 정적 변수

# 인접 리스트 
for _ in range(E):
    A, B = map(int, input().split())
    adjlist[A].append(B)
    adjlist[B].append(A)

# 아직 탐색하지 않은 노드를 루트로 DFS 탐색
for v in range(1, V + 1):
    if discover[v] == 0:
        DFS(v, 1)

# 단절점 개수 출력
ans = sum(cut)
print(ans)

# 단절점 노드 번호 출력
for v in range(1, V + 1):
    if cut[v] == 1:
        print(v, end=' ')

위 코드에서 discover 리스트는 DFS 탐색 때 발견 순서로 번호가 매겨진다. ret 값은 해당 노드에서 더 탐색 가능한 노드들에서 얻을 수 있는 discover 값 중 최솟값을 가지게 된다.

이때, 특정 노드 X에서 ret값이 X의 discover 번호보다 크다면 노드 X는 단절점이 된다.

아래 루트 노드에 대한 예외 처리도 해주었다. (DFS 함수의 인자인 isroot가 True이면 루트 노드이다)

결과