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

문제

풀이

유니온파인드 문제이다

유니온파인드(Union-find)

= 합집합 찾기 = 상호배타적 집합
여러노드가 존재할 때, 두 개의 노드를 선택해서 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
보통 parent[] 배열을 만들어서 각 노드의 parent들을 저장해놓는다

• find : x가 어떤 집합에 포함되어 있는지 찾는 연산
• union : x와 y가 포함되어 있는 집합을 합치는 연산

int find(int x) {
	if(x == parent[x]) return x;
    else return parent[x]=find(parent[x]);
}    

void union(int x, int y){
	x = find(x);
    y = find(y);
    if(x!=y){parent[y] = x;}
}

코드

static int[] parent;

각 노드마다 parent를 담는 배열을 준비

		FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        map = new int[N+1][N+1];
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j] = fr.nextInt();
                if(map[i][j] == 1) {
                    // union
                    union(i, j);
                }
            }
        }

parent[]를 각자가 자신이 부모가 되도록 초기화하고
1을 발견할 때 마다 union하여 부모를 업데이트한다

전체코드

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

public class Main {

    static int N, M;
    static int[][] map;
    static int[] parent;

    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        map = new int[N+1][N+1];
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j] = fr.nextInt();
                if(map[i][j] == 1) {
                    // union
                    union(i, j);
                }
            }
        }
        int parent = find(fr.nextInt());
        for (int i = 1; i < M; i++) {
            int cur = fr.nextInt();
            if(find(cur) != parent){ System.out.println("NO"); return;}

        }
        System.out.println("YES");

    }

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

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if(x>=y) parent[y] = x;
            else parent[x] = y;
        }
    }

    public static void main(String[] args) {
        input();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

유니온파인드 문제는 이론을 까먹어서 처음부터 다시 공부했다. 역시 오랜시간 문제를 풀지 않으면 까먹는다는 걸 새삼 다시 느꼈다. 생각날 때마다 블로그에 쓴 문제들을 다시 읽어보면서 까먹지 않도록 하자