문제
N개의 도시와 M개의 도로가 있는 그래프가 있다. 도시들을 순서대로 제거하는 쿼리가 N번 주어진다. 각 쿼리 이전 상태(즉, i번째 도시가 제거되기 전)에서 그래프가 하나로 연결되어 있으면 CONNECT, 아니면 DISCONNECT를 출력한다. 처음 상태(모든 도시 제거 전)도 출력한다.
입력
- 첫째 줄: N, M (도시 수, 도로 수)
- 다음 M줄: 도로로 연결된 두 도시 번호
- 다음 N줄: 제거할 도시 번호 (순서대로)
출력
- N+1줄: 각 상태에서 CONNECT 또는 DISCONNECT
예제
| 입력 | 출력 |
|---|---|
3 2 1 2 2 3 1 2 3 | CONNECT DISCONNECT DISCONNECT CONNECT |
풀이
도시 제거 쿼리를 역순으로 처리하는 오프라인 쿼리 기법과 Union-Find를 결합한다. 제거 순서를 뒤집어 도시를 추가하는 방식으로 변환한다.
- 모든 제거 순서(
ers배열)를 미리 입력받는다. - 역순(N-1부터 0)으로 처리: 도시를 복원(추가)하는 것처럼 시뮬레이션한다.
- 도시 n을 복원할 때, 이미 복원된 인접 도시와 Union-Find로 연결한다.
- 연결이 성립할 때마다 컴포넌트 수(
cnt)를 감소시킨다. cnt == 1이면 해당 시점의ans[i] = true(CONNECT)로 기록한다.- 최종적으로 원래 순서(0~N)로 답을 출력한다.
핵심 아이디어: "제거" 쿼리를 직접 처리하는 것은 어렵다. 역방향으로 보면 "추가" 쿼리가 되고, 추가는 Union-Find로 효율적으로 처리할 수 있다. 오프라인 쿼리로 미리 모든 입력을 받고 역순 처리 후 결과를 뒤집는 것이 핵심이다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day106BOJ25172졸업여행 { // 25172 졸업여행
static int N, M, cnt;
static int[] p, ers;
static boolean[] ans, ext;
static List<Integer>[] edges;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
cnt = 0;
p = new int[N];
ers = new int[N];
ans = new boolean[N + 1];
ext = new boolean[N];
edges = new ArrayList[N];
for (int i = 0; i < N; i++) {
p[i] = i;
edges[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
edges[a].add(b);
edges[b].add(a);
}
for (int i = 0; i < N; i++)
ers[i] = Integer.parseInt(br.readLine()) - 1;
ans[N] = false;
for (int i = N - 1; i >= 0; i--) {
int n = ers[i];
ext[n] = true;
cnt++;
for (int c : edges[n]) {
if (!ext[c])
continue;
if (unionSet(n, c))
cnt--;
}
if (cnt == 1)
ans[i] = true;
}
for (int i = 0; i < N + 1; i++)
sb.append(ans[i] ? "CONNECT" : "DISCONNECT").append("\n");
System.out.println(sb);
br.close();
}
private static boolean unionSet(int a, int b) {
a = findSet(a);
b = findSet(b);
if (a == b)
return false;
p[b] = a;
return true;
}
private static int findSet(int a) {
return p[a] = (a == p[a]) ? a : findSet(p[a]);
}
}복잡도
- 시간: O(N α(N)) — α는 역아커만 함수 (실질적으로 상수)
- 공간: O(N)