[SW expert Academy] SWEA 7465번 창용 마을 무리의 개수 자바(Java)

[D4] 창용 마을 무리의 개수 - 7465

문제 링크

성능 요약

메모리: 26,272 KB, 시간: 139 ms, 코드길이: 1,772 Bytes

제출 일자

2023-12-27 14:26

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

 

풀이 방법

1. 아는 관계이거나 몇 사람을 거쳐서 알 수 있다. (= 전부 연결되어 있다.)

2. 무리의 개수를 카운트해야한다.

3. 같은 관계는 반복해서 주어지지 않는다.

4. dfs를 통해 방문처리해주면 된다.

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

class Solution {
    static boolean[][] graph;
    static boolean[] visit;
    static int n;
	public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            graph = new boolean[n+1][n+1];
            visit = new boolean[n+1];
            
            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][b] = graph[b][a] = true;
            }
            
            int result = 0;
            for(int i = 1; i <= n; i++){
                if(!visit[i]){
                    result++;
                    dfs(i);
                }
            }
			sb.append("#" + tc + " " + result).append("\n");
		}
        System.out.println(sb);
	}
    private static void dfs(int start){
        Stack<Integer> stack = new Stack<>();
        visit[start] = true;
        stack.push(start);
        
        while(!stack.isEmpty()){
            int cur = stack.pop();
            for(int i = 1; i <= n; i++){
                if(graph[cur][i] && !visit[i]){
                    stack.push(i);
                    visit[i] = true;
                }
            }
        }
    }
}