글 읽기 - union-find 문제 질문합니다..ㅠㅠ 도와주세요ㅜㅜ

dbrkgml97 3년 전 0

문제는 Union-Find로 풀었습니다.

배열의 index는 1 ~ N 으로 사용하였습니다.

[문제풀이 방식]

1. Array.fill을 통해 capital에 있는 모든 값을 -1 로 초기화 시켰습니다.

2. union을 통해 연결시켜줍니다.

3. (#1.)이라고 적혀진 부분의 코드는 루트노드를 자신의 index로 바꾸는 과정입니다.

4. 입력을 받으면서, 루트노드가 다른 것이 하나라도 있으면 NO를 출력하고 return

5. 루트노드가 모두 같으면 YES를 출력합니다.

이렇게 풀었는데, 반례를 못찾겠습니다.

틀렸습니다로 뜹니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[] capital;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        capital = new int[202];
        int connect, route;

        Arrays.fill(capital, -1);

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                connect = Integer.parseInt(st.nextToken());
                if(connect == 1) {
                    union(i, j);
                }
            }
        }

        //#1. 루트 노드를 자신을 가리키게 합니다. 
        for(int i=1; i<=N; i++) {
            if(capital[i] == -1)
                capital[i] = i;
        }

        st = new StringTokenizer(br.readLine());
        route = Integer.parseInt(st.nextToken());
        route = capital[route];

        for(int i=1; i<M; i++) {
            int a = Integer.parseInt(st.nextToken());

            //루트의 값이 다르면,
            if(route != capital[a]) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    public static int find(int n) {
        if(capital[n] < 0) return n;
        capital[n] = find(capital[n]);
        return capital[n];
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) return;

        capital[b] = a;
    }
}

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

문제

문제

출처

ICPC

union-find 문제 질문합니다..ㅠㅠ 도와주세요ㅜㅜ

dbrkgml97 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말