[SW Experts Academy]7465. 창용 마을 무리의 개수 - (Java풀이)

<서론>

이번에 포스팅하는 알고리즘 문제는 최근 스터디를 진행하게 되면서 첫번째 과제로 하게 된 세 문제 중, 가장 난이도 낮은 문제다. SW Experts Academy에서 제공하는 문제 중 D4 난이도의 문제는 몽땅 다 풀어버려야지! 하는 마음 가짐으로 접근했는데, 생각보다 쉽지 않았다. 아무튼 각설하고 가장 쉽게 풀었던 7465번 문제를 본격적으로 포스팅하겠다.

 

참고로 문제 링크는..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE

SW Expert Academy

 

---

 

<본론>

첫번째와 마찬가지로 완성 코드는 결론에 놓겠다.

알고리즘 문제 풀이의 첫번째 글의 문제를 풀었을 때보다 2달이 지난 다음에 풀어서 그런지, DFS 문제는 손쉽게 풀 수 있게 된 것 같다(물론, 이번 문제가 특히 더 쉽다).  다른 방법으로 풀 수도 있겠지만 가장 빨리 생각난 방법으로 문제를 풀었다.

 

큰 틀은 이렇다.

이 문제는 서로 알고 지내는 무리가 몇 개인지 구하는 문제인데, 이는 결국 그래프의 개수를 구하는 문제라고 생각했다.

따라서,

1. 임의의 노드에서 DFS 방법으로 완전 탐색을 진행한다.

2. 완전 탐색이 다 끝난 후에도 아직 방문하지 노드가 있는 지 확인한다.

3. 만약 방문하지 않은 노드가 있다면, 이것은 다른 그래프가 또 존재한다는 뜻.

4. 다른 노드를 정해서 완전 탐색을 진행한다.

5. 1~4 반복

 

이것보다 더 최적의 방법이 있을 수도 있다고 생각하지만, 일단 내가 생각할 수 있는 선에서는 이것이 베스트였다. 사실 다른 방법은 생각도 못했지만...

같이 스터디를 진행하는 팀원은 이 문제를 Union find로 풀었다. 처음 들어보는 알고리즘이었다. Union find가 무엇인지 공부하고 그 방법으로도 풀어봐야겠다.

 

---

 

<결론>

요약

 1. N을 입력 받고, N*N 크기의 2차 배열(graph), N 크기의 배열(visited), 정답으로 쓸 ans(초기값 1) 생성

 2. 1번부터 시작해서 DFS 방법으로 완전 탐색

 3. 완전 탐색 후 visited 배열에 false값 있는지 확인

  3.1 false값이 있는 경우 ans++ 후 break

 4. ans 값 출력

import java.util.Scanner;
 
class Solution
{
    static int[][] graph;
    static boolean[] visited;
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int n = sc.nextInt();
            int m = sc.nextInt();
            graph = new int[n+1][n+1];
            int ans = 1;
            visited = new boolean[n+1];
            for(int i=0; i<m; i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                graph[a][b] = 1;
                graph[b][a] = 1;
            }
            for(int i=1; i<n+1; i++){
                if(!visited[i]){
                    dfs(i, n+1);
                    for(int j=1; j<n+1; j++) {
                        if(!visited[j]) {
                            ans++;
                            break;
                        }
                    }
                }
            }
            System.out.println("#"+test_case+" "+ans);
        }
        sc.close();
    }
 
    static void dfs(int n, int tot) {
        if(!visited[n]) {
           visited[n] = true;
           for(int i=1; i<tot; i++){
               if(graph[n][i]==1 && !visited[i]) dfs(i, tot);
           }
        }
    }
}