본문 바로가기

카테고리 없음

[백준 11266번] 단절점 (Python3)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def DFS(now,last):
  global id
  visited[now] = ID[now] = id
  cnt = 0; check = 0
  for next in graph[now]:
    if next==last:
      continue
    if visited[next]:
      visited[now] = min(visited[now],ID[next])
    else:
      cnt += 1; id += 1
      DFS(next,now)
      if visited[next] >= ID[now]:
        check = 1
      visited[now] = min(visited[now],visited[next])
  if ID[now]!=1 and check or ID[now]==1 and cnt>1:
    point.append(now)

N,M = map(int,input().split())

graph = [[] for i in range(N+1)]
for _ in range(M):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [0]*(N+1); ID = [0]*(N+1)
point = []
for i in range(1,N+1):
  if not visited[i]:
    id = 1
    DFS(i,i)

print(len(point))
if point:
  print(*sorted(point))

단절점 알고리즘 기본문제이다.

알고리즘에 대한 설명은 https://www.crocus.co.kr/1164 여기를 참고하였다.

알고리즘에 대한 설명을 읽고 SCC와 별 다를게 없다고 생각했다. 그래서 쉽게 코드를 짰는데 계속해서 실수가 나왔다. 그러다 보니 무려 13번이나 틀렸습니다! 끝에 겨우겨우 맞출 수 있었다.

실수의 흔적...

정확하게 이해를 하지 않고 문제를 풀게 되면 구현과정에서 여러가지 실수가 나올 수 있는 문제이다.

 

일단 내가 한 실수를 정리하면,

1. 출력초과의 경우 단절점이 없는 경우에 한줄 더 출력해서 발생하였다. 단절점이 없을때는 0 한줄만을 출력해야한다.

2. 현재 노드가 이전에 탐색한 노드로 갈 수 있는지가 아니라 현재 노드의 "자식"이 이전에 탐색한 노드로 갈 수 있는지를 확인해야 한다.

3. 현재 노드의 자식이 2개 이상이더라도 루트노드가 아니라면 단절점이 아닐 수 있다. 조건문을 명확하게 명시하자.

4. visited를 갱신할 때, visited[next]로 갱신해선 안된다. 자식노드의 경우 visited로 갱신하고, 이미 탐색한 노드라면 ID로 갱신해야한다. (참고 https://www.acmicpc.net/board/view/34811)

5. 내가 실수한 부분은 아니지만 주어진 그래프가 연결그래프가 아닐 수 있음에 주의하자

 

 

오늘의 교훈) 단절선을 풀어보자