[python] baekjoon 11400 : 단절선

문제

-> 문제 링크 : https://www.acmicpc.net/problem/11400

11400번: 단절선

 

문제풀이

단절선은 제거했을 때 그래프가 여러 개로 나눠지는 간선을 의미한다.

 

단절선 문제를 해결하기 위해서는 트리의 부모, 자식의 개념을 이용하면 쉽다.

dfs를 이용해 방문 순서대로 정점에 순서를 매긴다고 하자. 이때 자식의 정점 순서는 부모의 정점 순서 + 1이 된다.

 

이때 현재 간선이 없다고 가정하고, 자식 정점에서부터 접근 가능한 모든 정점들의 순서의 최솟값을 구했을 때 자식 정점의 순서보다 크다면 현재 간선은 단절선이 된다.

 

이를 구현하기 위해 dfs를 재귀로 구현한다.

dfs의 입력 파라미터로 현재 정점과 간선으로 이어진 부모 정점을 받는다.

현재 정점이 방문 가능한 정점 중 부모 정점으로 가는 간선은 제외하고 방문하지 않은 정점에 대해서 dfs 재귀로 방문하게 된다.

이때 dfs의 반환값은 현재 정점에서부터 접근할 수 있는 정점의 최소 순서를 반환하게 된다. 

 

dfs 내부에서는 반복문을 통해 현재 정점을 부모로 하고 접근 가능한 모든 자식 정점이 가질 수 있는 최소 순서를 살펴본다.

만약 모든 반환값이 자신의 순서보다 크다면 접근 가능한 정점들 중에 선조로 가는 간선이 존재하지 않는 것이니 단절선이 된다.

이때 주의해야할 점은 dfs의 반환값은 방문할 수 있는 정점에 대해서만 나온다는 것이다.

자식 정점이 이미 방문하여 dfs를 통해 갈 수 없다면 자식 정점의 순서가 이 자식 정점이 가질 수 있는 최소 순서가 된다

 

코드

import sys
from collections import defaultdict

sys.setrecursionlimit(10**6)

def dfs(here, parent):
	global cnt
	cnt += 1
	order[here] = cnt
	ret = order[here]

	for next in graph[here] :
		if next == parent :
			continue

		if order[next] :
			ret = min(ret, order[next])
			continue

		subtree = dfs(next, here)
		ret = min(subtree, ret)

		# 부모로 바로가는 간선(현재간선)을 제외하고 서브트리의 간선 중 부모보다 선조로 갈 수 없으면
		if subtree > order[here] :
			cutEdge.add(tuple(sorted([here,next])))

	return ret


# N개
V,E = map(int, sys.stdin.readline().rstrip().split(" "))
graph = defaultdict(set)
cutEdge = set()
candidates = set()

for _ in range(E) :
    a,b = map(int, sys.stdin.readline().rstrip().split(" "))
    graph[a].add(b)
    graph[b].add(a)
    candidates.add(a)
    candidates.add(b)

order = [None] * (V+1)
cnt = 0
idx =0
for vertex in candidates :
    if not order[vertex] :
        dfs(vertex,  None)


print(len(cutEdge))
cutEdge = sorted(cutEdge, key=lambda x : (x[0],x[1]))

for a,b in cutEdge :
    print(a,b)

초기 접근 방식과 오답의 원인

흠..

 

2코드에 잘못된 부분이나 개선 사항을 댓글로 알려주시면 감사하겠습니다.