[자바] 백준 16965 - 구간과 쿼리 (java)

목차

문제 : boj16965

 

 

필요 알고리즘

• 너비 우선 탐색 (bfs)
  
  • 뭔가 bfs와 관련없어 보이지만, bfs 문제이다!

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  BFS를 모른다면 우선 '이 글'을 참고해보자.

결국 이 문제에서 중요한건 '구간 (x1, y1)에서 구간 (x2, y2)로 이동하려면 x2 < x1 < y2 또는 x2 < y1 < y2를 만족' 이 부분이다. 처음엔 서로소 집합 (disjoint set)으로 생각했었는데, 틀렸다고 떠서 생각해보니 구간 l1이 구간 l2를 완전히 포함시킨다고 할 때, 한쪽에서만 이동이 가능하므로 양방향으로 이동 가능하다고 하는셈인 서로소 집합으로는 풀 수 없는게 맞다.

 

  따라서 단방향으로 생각해야 했고, 어차피 N이 100밖에 안되므로 매번 BFS 등의 그래프 탐색으로 해도 문제 없을 것 같았다. 그래서 이하와 같이 로직을 진행했다.

 

1. N개의 쿼리를 입력받는다.

 

 

2. 쿼리가 '2'로 시작한다면 BFS를 진행해서 답을 출력한다.

private boolean isReachable(final int from, final int to) {
    boolean[] v = new boolean[n+1];
    v[from] = true;

    Queue<Integer> q = new ArrayDeque<>();
    q.add(from);
    while (!q.isEmpty()) {
        int cur = q.poll();

        for (int next : edges[cur]) {
            if (next == to) return true;

            if (v[next]) continue;
            v[next] = true;

            q.add(next);
        }
    }
    return false;
}

 

3. 쿼리가 '1'로 시작할 경우 지금까지 입력으로 들어온 쿼리들 모두를 확인하며 단방향 간선을 생성한다.

int curIth = ++ith;
for (Order order : orders) {
    if (order.a < a && a < order.b || order.a < b && b < order.b)
        edges[curIth].add(order.ith);
    if (a < order.a && order.a < b || a < order.b && order.b < b)
        edges[order.ith].add(curIth);
}
orders.add(new Order(curIth, a, b));

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    int n;
    List<Integer>[] edges;
    private void solution() throws Exception {
        n = Integer.parseInt(br.readLine());
        edges = new List[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();

        int ith = 0;
        List<Order> orders = new ArrayList<>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (op == 2) {
                sb.append(isReachable(a, b) ? 1 : 0).append('\n');
                continue;
            }

            int curIth = ++ith;
            for (Order order : orders) {
                if (order.a < a && a < order.b || order.a < b && b < order.b)
                    edges[curIth].add(order.ith);
                if (a < order.a && order.a < b || a < order.b && order.b < b)
                    edges[order.ith].add(curIth);
            }
            orders.add(new Order(curIth, a, b));
        }

        System.out.print(sb);
    }

    private boolean isReachable(final int from, final int to) {
        boolean[] v = new boolean[n+1];
        v[from] = true;

        Queue<Integer> q = new ArrayDeque<>();
        q.add(from);
        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int next : edges[cur]) {
                if (next == to) return true;

                if (v[next]) continue;
                v[next] = true;

                q.add(next);
            }
        }
        return false;
    }
}

class Order {
    int ith, a, b;
    public Order(int ith, int a, int b) {
        this.ith = ith;
        this.a = a;
        this.b = b;
    }
}