[SWEA | Java] 7465번 창용 마을 무리의 개수

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

SW Expert Academy

티어

소요 시간

7분

분류

dfs

find-union

코드

DFS

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

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

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            ArrayList<Integer>[] graph = new ArrayList[n + 1];
            for (int i = 1; i<= n; i++) graph[i] = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                graph[a].add(b);
                graph[b].add(a);
            }

            boolean[] visited = new boolean[n + 1];
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    findGroup(graph, visited, i);
                    cnt++;
                }
            }

            System.out.println("#" + test + " " + cnt);
        }
    }

    private static void findGroup(ArrayList<Integer>[] graph, boolean[] visited, int root) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            visited[poll] = true;

            for (Integer friend : graph[poll]) {
                if (!visited[friend]) {
                    queue.add(friend);
                }
            }
        }
    }
}

Find-Union

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

public class Solution {

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

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            ArrayList<int[]> graph = new ArrayList<>();
            int[] root = new int[n + 1];
            for (int i = 1; i<= n; i++) {
                root[i] = i;
            }
            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                graph.add(new int[]{a, b});
            }

            for (int i = 0; i < m; i++) {
                int[] relationship = graph.get(i);
                int a = relationship[0], b = relationship[1];

                if (find(root, a) != find(root, b)) union(root, a, b);
            }

            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                if (root[i] == i) cnt++;
            }

            System.out.println("#" + test + " " + cnt);
        }
    }

    private static void union(int[] root, int v1, int v2) {
        int p1 = root[v1];
        int p2 = root[v2];

        if (p1 != p2) root[p2] = p1;
    }

    private static int find(int[] root, int v) {
        if (root[v] == v)
            return v;
        else
            return root[v] = find(root, root[v]);
    }
}

코드 설명

같은 무리일 경우 인접한 노드를 탐색할 때 함께 탐색된다

이는 dfs의 관점에서 보았을 때 visited가 true로 된다는 뜻이고,

find-union의 관점에서 보았을 때 parent 혹은 root 배열의 원소가 한 곳을 가리키게 된다는 뜻이다. (조상이 같다)