문제
통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다.
예를 들어 <그림 1>에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.)
<그림 1>
통나무들의 위치를 입력받아 질문으로 주어진 통나무들의 쌍에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한지 판단하는 프로그램을 작성하라.
입력
첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무의 x₁, x₂, y가 주어진다. 주어진 통나무는 두 점 (x₁, y)와 (x₂, y)를 잇는 형태이며, 항상 x₁ < x₂를 만족한다. 모든 좌표는 0 이상 10^9 이하이다. 통나무들은 주어진 순서대로 1번부터 번호가 붙어 있다. 서로 다른 두 통나무는 끝점에서도 만나지 않는다. 다음 Q개의 줄에 서로 다른 두 통나무의 번호가 주어진다. (1 <= N <= 100,000, 1 <= Q <= 100,000)
출력
Q개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 질문에 주어진 두 통나무에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한 경우 대답은 1, 그렇지 않은 경우 대답은 0이다.
풀이
점프 가능 여부를 직접 그래프로 만들면 복잡해 보이지만, 실제로는 x축 구간이 이어져 있는 통나무들은 모두 같은 연결 요소로 볼 수 있다.
코드에서는 통나무를 x1 기준으로 정렬한다. 그리고 왼쪽부터 보면서 현재까지 이어진 구간의 가장 큰 x2 값을 maxX2로 관리한다. 다음 통나무의 x1이 maxX2 이하라면 x축 구간이 겹치거나 닿아 있으므로 같은 그룹으로 union 한다.
반대로 x1 > maxX2라면 이전 묶음과는 완전히 끊긴 새로운 그룹이 시작된 것이다. 이렇게 한 번 훑고 나면, 이후 질의는 두 통나무의 대표가 같은지만 보면 된다.
즉 이 문제는 기하 문제처럼 보여도, 정렬 + 스위핑 + union-find로 정리할 수 있다.
코드
import java.io.*;
import java.util.*;
public class Main {
static class Node implements Comparable<Node> {
int idx, x1, x2, y;
Node (int idx, int x1, int x2, int y) {
this.idx = idx;
this.x1 = x1;
this.x2 = x2;
this.y = y;
}
@Override
public int compareTo(Node o) {
if (this.x1 == o.x1) {
if (this.x2 == o.x2)
return this.y - o.y;
return o.x2 - this.x2;
}
return this.x1 - o.x1;
}
}
static List<Node> list;
static int[] parent;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
parent = new int[N + 1];
for (int i = 1; i <= N; i++)
parent[i] = i;
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
list.add(new Node(i, x1, x2, y));
}
Collections.sort(list);
System.out.println(solve(N, Q));
}
static String solve(int N, int Q) throws IOException {
StringBuilder sb = new StringBuilder();
Node cur = list.remove(0);
int maxX2 = cur.x2;
int maxIdx = cur.idx;
for (Node node : list) {
if (maxX2 >= node.x1) {
union(maxIdx, node.idx);
maxX2 = Math.max(maxX2, node.x2);
} else {
maxX2 = node.x2;
maxIdx = node.idx;
}
}
while(Q-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int ans = 0;
if (find(start) == find(end))
ans = 1;
sb.append(ans).append('\n');
}
return sb.toString();
}
static int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (a < b) parent[b] = a;
else parent[a] = b;
}
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
통나무의 높이보다 중요한 건 x축 구간이 이어지는지 여부였다. 한 번 정렬해서 묶음을 만들고 나면, 이후 질의는 union-find 조회로 아주 가볍게 끝난다.
