백준 16965 - 구간과 쿼리

문제

https://www.acmicpc.net/problem/16965

리뷰

BFS를 통하여 풀이할 수 있는 문제였다.

먼저 각 구간을 나타내기 위해 시작점(s)과 끝점(e)을 필드로 가지는 클래스 Pair를
산정하였다. 이 구간들은 List에 저장하였으며 구간의 List 인덱스와 visited의
인덱스는 동일하다.

이후, 2 쿼리에 대하여 visited 배열의 크기를 현재까지 저장된 구간의 개수
(graph의 size)로 초기화하고 BFS 로직내에서 이동할 수 있는 구간의 조건에 부합하는
경우만 탐색을 진행하며 주어진 구간에 도달할 수 있는 경우를 판별하도록 로직을 구성하였다.

로직의 시간복잡도는 BFS 부분에서 $O(N^2)$ 형태로 수렴하고 $N=100$인 최악의 경우에도
무난히 1초의 제한 조건을 통과한다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static boolean[] visited;
    static List<Pair> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = parseInt(br.readLine());
        int q, x, y, a, b;

        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            q = parseInt(st.nextToken());
            if (q == 1) {
                x = parseInt(st.nextToken());
                y = parseInt(st.nextToken());

                graph.add(new Pair(x, y));
            } else {
                a = parseInt(st.nextToken()) - 1;
                b = parseInt(st.nextToken()) - 1;

                visited = new boolean[graph.size()];
                Arrays.fill(visited, false);
                sb.append(bfs(a, b) ? 1 : 0).append("\n");
            }
        }

        System.out.print(sb);
        br.close();
    }


    static boolean bfs(int start, int end) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            if (cur == end) return true;

            Pair p = graph.get(cur);

            for (int idx = 0; idx < graph.size(); idx++) {
                if (visited[idx]) continue;

                Pair pair = graph.get(idx);
                if (pair.s < p.s && p.s < pair.e || pair.s < p.e && p.e < pair.e) {
                    visited[idx] = true;
                    queue.offer(idx);
                }
            }
        }

        return false;
    }


    static class Pair {
        int s, e;

        public Pair(int s, int e) {
            this.s = s;
            this.e = e;
        }
    }
}

결과