글 읽기 - 예외를 모르겠습니다..휴

exponential_e 3년 전 0

문제를 잘못 이해한 걸까요.. 물론 다른 방법도 가능할 것 같지만 이 방법이 왜 안되는지 알고싶어서 질문 드려봅니다. 서로소 집합 사용했습니다.

코드를 잘못 짠건지 애초에 서로소 집합으로 안되는건지 모르겠네요.

우선,

1 x1 y1

1 x2 y2

이와 같은 입력이 주어질 때 항상 x1 y1인 이전 구간보다 x2 y2 구간이 크다 했으므로 (x1 == x2 && y1 == y2) 인 경우는 없을 테니,

문제 조건과 상응하는 것 같고 따라서 등호 없이 맞춰 넣었습니다. 조건을 충족하면 같은 집합으로 묶었구요.

원래는 쿼리로 추가되는 구간만 그때그때 확인해서 집합으로 넣었는데, 자꾸 틀려서 그냥 무식하게 구간 추가할 때마다 중첩 반복문 돌렸습니다.

그래도 틀렸지만요 ㅎㅎ..

자료형 오버플로우인가 했더니.. 모두 정수형으로 들어오니까 문제는 없어보이는데 채점 시작과 동시에 나가리 당하네요 ㅠ

문제 설명에서 N을 제외하곤 10억이라고 했는데

2 i j -> 이러한 쿼리가 들어오면 'i번째 j번째 구간이 서로 이동 가능한 구간이냐'라고 물어보는 것으로 이해했는데 이러면 i, j 값도 N 이하의 값일 것 이라 생각했습니다.

이게 잘못 생각 한걸까요.. 모르겠네요

반례가 있다면 도움 부탁드립니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final String NEW_LINE = "\n";
    private static int[] parent;

    private static class Pair {
        int idx;
        int from;
        int to;

        public Pair(int idx, int from, int to) {
            this.idx = idx;
            this.from = from;
            this.to = to;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        parent = new int[N];
        Arrays.fill(parent, -1);

        StringBuilder sb = new StringBuilder();
        ArrayList<Pair> section = new ArrayList<>();

        int count = 0;

        while (N-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            if (cmd == 1) {
                section.add(new Pair(count++, f, t));
                checkSection(section);
            }
            else {
                sb.append(find(f - 1) == find(t - 1) ? 1 : 0).append(NEW_LINE);
            }
        }

        System.out.println(sb.toString());
    }

    private static void checkSection(ArrayList<Pair> sec) {
        for (Pair current: sec) {
            for (Pair another: sec) {
                if ((current.from < another.from && another.from < current.to)
                        || (current.from < another.to && another.to < current.to)) {

                    merge(another.idx, current.idx);
                }
            }
        }
    }

    private static int find(int x) {
        if (parent[x] < 0) return x;
        else return parent[x] = find(parent[x]);
    }

    private static void merge(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return;

        if (parent[x] < parent[y]) {
            parent[x] += parent[y];
            parent[y] = x;
        }
        else {
            parent[y] += parent[x];
            parent[x] = y;
        }
    }
}

chansol 2년 전 1

저도 이전에 Union-Find로 접근했다가 틀렸는데, 오늘 다시 문제를 보면서 잘못된 부분을 찾은 것 같습니다.

일반적으로 겹치는 경우라면, 서로 다른 두 구간끼리 오고 가는 것이 가능하지만,

어떤 한 구간이 다른 구간을 모두 포함하는 경우라면, 더 큰 구간에서 작은 구간으로 이동하는 것만 가능합니다.

그래서 그랬던 것 같습니다..

exponential_e 2년 전 0

아 그렇군요.. 그 조건을 너무 소홀히했군요.

다시 확인해봐야겠습니다. 답변 감사드립니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예외를 모르겠습니다..휴

exponential_e 3년 전 0

chansol 2년 전 1

exponential_e 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말