7465. 창용 마을 무리의 개수 - 자바(JAVA)

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

SW Expert Academy

 

문제 해석

마을에는 N명의 사람이 살고 있다.

사람들은 1번부터 N번까지 번호가 부여되어 있습니다

두 사람은 서로 알고 있는 관계일 수 있고, 아닐 수 있습니다.

두 사람이 서로 아는 사람이거나 몇 사람을 거쳐서 알 수 있는 관계라면 이러한 사람들을 모두 묶어 하나의 무리라고 합니다.

창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하세요.

 

문제 풀이 전 설계

입력을 통해 인접 행렬을 만들고

DFS를 통해 문제를 해결합니다.

1~N까지 반복하며 반복문을 도는 횟수만큼 무리의 수로 카운트합니다.

반복문의 수 == 무리의 수인 이유는 이미 방문하였다면 continue 처리를 해주기 때문에 이미 무리에 속해있다면 group++을 진행하지 않습니다.

 

코드

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

public class Solution_7465_창용마을무리의개수 {

	static boolean[][] graph;
	static boolean[] visited;
	static int N,M;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb= new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			graph = new boolean[N + 1][N + 1];
			visited = new boolean[N + 1];

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int personA = Integer.parseInt(st.nextToken());
				int personB = Integer.parseInt(st.nextToken());
				graph[personA][personB] = graph[personB][personA] = true;
			}

			int group = 0;
			for (int i = 1; i <= N; i++) {
				if (visited[i]) {
					continue;
				}
				group++;
				dfs(i);
			}
			sb.append("#" + tc + " " + group + "\n");
		}
		System.out.println(sb);
	}

	private static void dfs(int i) {
		visited[i] = true;
		for(int j=1; j<=N; j++) {
			if(graph[i][j] != true) {
				continue;
			}
			if(visited[j]) {
				continue;
			}
			dfs(j);
		}
	}

}