[BFS&DFS/Java] SWEA 7465. 창용 마을 무리의 개수

해석

이 문제는 인접 리스트를 이용하여 relation group의 개수를 묻는 문제이다. 따라서 그래프 탐색을 통해 연관 노드를 한번에 방문하는 방식으로 로직을 전개하면 마을의 개수를 구할 수 있다.

보통 격자 상에서의 그래프 알고리즘이 아닌, 이 문제와 같이 인접 행렬 또는 인접 리스트를 활용하는 그래프 알고리즘의 시간복잡도는 인접 행렬과 리스트 각각 O(v^2), O(v + e)이다. 이는 아래 구현된 로직에서도 확인할 수 있다.

노드의 개수가 최대 100개라고 주어져 있으므로, 인접 행렬이든 리스트든 관련 없이 문제를 풀 순 있었을 것이다. 간선의 개수는 n(n-1)/2개라고 되어있으므로 인접 행렬로 구현하였다.

풀이

DFS

package ssafy.사전학습.그래프;  

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

public class 창용_마을_무리의_개수 {  
    private static boolean[] visited;  
    private static int[][] graph;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int t = Integer.parseInt(st.nextToken());  
        for (int i = 1; i <= t; i++) {  
            st = new StringTokenizer(br.readLine());  
            int n = Integer.parseInt(st.nextToken());  
            int m = Integer.parseInt(st.nextToken());  
            visited = new boolean[n];  
            graph = new int[n][n];  

            // 인접 리스트 초기화  
            for (int j = 0; j < m; j++) {  
                st = new StringTokenizer(br.readLine());  
                int a = Integer.parseInt(st.nextToken()) - 1;  
                int b = Integer.parseInt(st.nextToken()) - 1;  
                graph[a][b] = b;  
                graph[b][a] = a;  
            }  

            int ans = 0;  
            for (int j = 0; j < n; j++) {  
                if (!visited[j]) {  
                    ans += dfs(j); // edit-point
                }  
            }  
            System.out.println("#" + i + " " + ans);  


        }  

    }  

    private static int dfs(int start) {  
        for (int v : graph[start]) {  
            if (v > 0 && !visited[v]) {  
                visited[v] = true;  
                dfs(v);  
            }  
        }  
        return 1;  
    }  
}

BFS

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

public class 창용_마을_무리의_개수 {  
    private static boolean[] visited;  
    private static int[][] graph;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int t = Integer.parseInt(st.nextToken());  
        for (int i = 1; i <= t; i++) {  
            st = new StringTokenizer(br.readLine());  
            int n = Integer.parseInt(st.nextToken());  
            int m = Integer.parseInt(st.nextToken());  
            visited = new boolean[n];  
            graph = new int[n][n];  

            // 인접 리스트 초기화  
            for (int j = 0; j < m; j++) {  
                st = new StringTokenizer(br.readLine());  
                int a = Integer.parseInt(st.nextToken()) - 1;  
                int b = Integer.parseInt(st.nextToken()) - 1;  
                graph[a][b] = b;  
                graph[b][a] = a;  
            }  

            int ans = 0;  
            for (int j = 0; j < n; j++) {  
                if (!visited[j]) {  
                    ans += bfs(j); // edit-point
                }  
            }  
            System.out.println("#" + i + " " + ans);  


        }  

    }  

    private static int bfs(int start) {  
        Queue<Integer> q = new LinkedList<>();  
        q.add(start);  
        visited[start] = true;  
        while (!q.isEmpty()) {  
            Integer now = q.poll();  
            for (int v : graph[now]) {  
                if (!visited[v]) {  
                    q.add(v);  
                    visited[v] = true;  
                }  
            }  
        }  
        return 1;  
    }  
}