[백준/25172] 꼼꼼한 쿠기의 졸업여행 (Python)

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

25172번: 꼼꼼한 쿠기의 졸업여행

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:20:50

 

---

 

문제 설명

 

 

가톨릭대학교 학생인 쿠기는 졸업을 앞두고 여행을 가기로 결심했다. 꼼꼼한 성격인 쿠기는 여행을 가기 전에 여행계획을 미리 세우려 한다.

우선 쿠기는 가고 싶은 관광지를 모두 골라 여행지도를 그려봤다. 여행지도는 1부터 N까지의 서로 다른 번호를 가진 N개의 관광지가 있으며, 서로 다른 두 관광지를 오갈 수 있는 M개의 길들로 이루어져 있다. 이때, 모든 관광지는 여러 번 방문이 가능하다.

쿠기는 여행예산이 이미 정해져 있기 때문에 아쉽지만 여행지도에서 관광지를 하나씩 제외해보며 여행계획을 세우려 한다. 만약, 어떤 관광지를 제외했다면, 제외한 관광지와 연결된 모든 길도 여행지도상에서 제외가 된다. 또한, 제외된 관광지와 길은 여행지도에서 영구적으로 제외가 된다.

쿠기가 생각하는 이상적인 여행계획은 여행지도에 반드시 하나 이상의 관광지가 존재하고 임의의 관광지에서 다른 어떤 관광지도 모두 도달할 수 있어야 한다. 쿠기를 도와 여행지도에서 관광지를 계속해서 하나씩 제외했을 때 이상적인 여행계획이 되는지 확인해보자.

 

 

입력 및 출력

 

입력

 

첫번째 줄에는 여행지도에 있는 관광지의 수 N(1 ≤ N ≤ 200,000)와 두 관광지 사이를 연결하는 길의 수 M(1 ≤ M ≤ min(N×(N-1)/2, 200,000))가 주어진다.

다음 M개의 줄에는 쿠기가 그린 여행지도에서 각각의 길이 연결하는 두 관광지의 번호가 주어진다. 단, 길은 중복해서 주어지지 않는다.

그 다음 N개의 줄에 제외할 관광지 리스트가 순서대로 주어진다.

 

출력

 

첫번째 줄에는 관광지를 단 하나도 제외하지 않았을 때 이상적인 여행계획이 되는지 확인한다.

그 다음 줄부터는 입력에서 주어지는 제외할 관광지 리스트 중 i번째 관광지를 제외했을 때 이상적인 여행계획이 되는지 확인한다. 

여행계획을 확인했을 때 이상적인 여행계획이라면 "CONNECT"아니면 "DISCONNECT"를 출력한다.

 

입력 예시

 

5 4
5 4
4 3
3 2
2 1
4
5
1
2
3

 

출력 예시

 

CONNECT
DISCONNECT
CONNECT
CONNECT
CONNECT
DISCONNECT

 

 

---

 

풀이

 

이 문제와 핵심 풀이는 놀랄 정도로 동일하다!

 

2024.01.25 - [PS/백준] - [백준/26155] 배수관 미스터리 (Python)

[백준/26155] 배수관 미스터리 (Python)

 

핵심 풀이는

• 노드를 하나씩 삭제하면서 모든 경우를 검사하는 것은 시간복잡도상 매우 커지므로
• 오프라인 쿼리를 적용하여 거꾸로 노드를 하나씩 추가하면서
• 이 노드와 연결된 엣지들을 union-find를 통하여 합친 후, 그 결과인 그래프가 1개로 이루어지는지 검사

로 거의 동일하다. 여기서 그래프의 루트 노드들을 저장해두고, 노드를 하나 추가하였을 때 루트 노드들의 개수를 갱신하여 세면 그래프의 개수를 셀 수 있다. 만약 노드의 추가로 인하여 둘 이상의 그래프가 연결되었다면 루트 노드가 하나로 통합될 것이고, 노드가 연결되지 않은 채 그대로라면 루트 노드가 하나 늘어나는 효과를 가질 것이다. 총 시간복잡도는 O(N+M)이 된다. (엣지를 최대 2M번 확인하게 되고, 이 엣지 확인 연산이 N번 이루어지게 된다)

 

풀이 코드

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

N, M = map(int, input().split())
parents = list(range(N+1))
edge_dict = defaultdict(list)

for _ in range(M) : 
  a, b = map(int, input().split())
  edge_dict[a].append(b)
  edge_dict[b].append(a)

visited = [False] * (N+1)
graph = set()
connect_queue = [int(input()) for _ in range(N)]

def find(a) :
  if parents[a] == a :
    return a
  parents[a] = find(parents[a])
  return parents[a]

def union(a, b) :
  pa, pb = find(a), find(b)
  if pa > pb :
    pa, pb = pb, pa
  parents[pb] = pa
  return

def is_full_connected(n) :
  global graph
  visited[n] = True
  graph.add(n)
  for m in edge_dict[n] :
    if visited[m] :
      union(m, n)

  graph = { find(g) for g in graph }
  return len(graph) == 1

ans = ["DISCONNECT"]
for n in reversed(connect_queue) :
  res = "CONNECT" if is_full_connected(n) else "DISCONNECT"
  ans.append(res)

print(*reversed(ans), sep='\n')

풀이 완료!