[백준/11266] 단절점 (Python)

Problem : https://www.acmicpc.net/problem/11266

11266번: 단절점

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:32:18

 

---

 

문제 설명

 

 

그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오.

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. 정점은 1부터 V까지 번호가 매겨져 있다.

 

출력

 

첫째 줄에 단절점의 개수를 출력한다.

둘째 줄에는 단절점의 번호를 공백으로 구분해 오름차순으로 출력한다.

 

입력 예시

 

7 7
1 4
4 5
5 1
1 6
6 7
2 7
7 3

 

출력 예시

 

3
1 6 7

 

 

---

 

풀이

 

단절점 기본 개념을 묻는 문제. 나도 이 개념을 오늘 문제풀이를 통해 학습하였기에, 학습 개념에 대해 정리하는 시간을 함께 가져보고자 한다.

 

단절점을 제거했을 때 그래프가 둘 이상으로 나눠진다는 말을 '트리 방문'의 형태로 생각해 보자. 현재 노드가 단절점인지 아닌지 판단하려면 어떻게 해야 할까? 단절점 이후에 방문하는 모든 노드들에 대해서 우회로가 존재하지 않아야 한다. 즉 방문 순서를 기록하였을 때, 자식 및 손자 노드들이 접근할 수 있는 모든 방문 순서를 탐색한다. 그리고 그 탐색 최솟값이 현재 방문 순서보다 낮다면 단절점이 아니고, 같거나 크다면 단절점이다. 그리고 마지막으로, 현재 탐색 최솟값을 반환하여 이전 노드들의 단절점 판단을 재귀적으로 해결하도록 한다.

 

만약 현재 노드가 루트 노드일 때는 더 간단하다. 모든 자식 노드들의 탐색 과정을 거치게 되면 현재 노드의 자식 개수를 구할 수 있으며, 자식 개수가 2개 이상이면 무조건 단절점이다.

 

 

 

 

풀이 코드

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MAX = float('inf')

V, E = map(int, input().split())
visit_order = [MAX]*V
order = 0
answer = set()
edge_dict = defaultdict(list)
for _ in range(E) :
  a, b = map(int, input().split())
  edge_dict[a-1].append(b-1)
  edge_dict[b-1].append(a-1)

def dfs(node, isroot) :
  global order
  visit_order[node] = order
  order += 1
  child_num = 0
  child_order = visit_order[node]
  
  for nxt in edge_dict[node] :
    if visit_order[nxt] < MAX :
      child_order = min(child_order, visit_order[nxt])
    else :
      child_num += 1
      tmp = dfs(nxt, False)
      if not isroot and tmp >= visit_order[node] :
        answer.add(node+1)
      child_order = min(child_order, tmp)
      
  if isroot and child_num >= 2 :
    answer.add(node+1)
  return child_order

for i in range(V) :
  if visit_order[i] == MAX :
    dfs(i, True)
answer = sorted(list(answer))
print(len(answer))
print(*answer)

풀이 완료!