SW Expert Academy - 7465번(창용 마을 무리의 개수)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=%EC%B0%BD%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

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

public class Solution {

	private static class Node {
		
		int vertex; // 정점
		Node next; 	// 다음 노드
		
		public Node(int vertex, Node next) {
			this.vertex = vertex;
			this.next = next;
		}
		
	}
	
	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(reader.readLine()); // 테케 개수
		
		for (int i = 0; i < T; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			int N = Integer.parseInt(tokenizer.nextToken()); // 노드 개수(사람 수)
			int M = Integer.parseInt(tokenizer.nextToken()); // 간선 개수(아는 사이 수)
			
			Node[] adjList = new Node[N + 1]; // 1-base index
			for (int j = 0; j < M; j++) {
				tokenizer = new StringTokenizer(reader.readLine());
				int from = Integer.parseInt(tokenizer.nextToken()); // 시작 정점
				int to = Integer.parseInt(tokenizer.nextToken());	// 끝 정점
				
				adjList[from] = new Node(to, adjList[from]);		// 인접 리스트 생성
				adjList[to] = new Node(from, adjList[to]);
			}
			
			int result = 0;
			
			boolean[] visited = new boolean[N + 1]; // 1-base index
			for (int j = 1; j < N + 1; j++) {
				if (!visited[j]) {
					dfs(adjList, visited, j);
					result++;
				}
			}
			
			sb.append("#").append(i + 1).append(" ");
			sb.append(result).append("\n");
		}
		
		System.out.println(sb);
	}
	
	private static void dfs(Node[] adjList, boolean[] visited, int current) {
		visited[current] = true;
		
		for (Node node = adjList[current]; node != null; node = node.next) {
			if (!visited[node.vertex]) {
				dfs(adjList, visited, node.vertex);
			}
		}
	}

}

• 사람을 그래프의 정점, 사람 사이의 아는 관계를 간선으로 생각하여 그래프 알고리즘을 통하여 해결할 수 있었다.
• 연결된 두 사람은 서로 아는 관계로 무향 그래프가 된다. 처음에 아무 생각없이 유향 그래프로 풀었다가 절반만 맞추었다.
• 그래프를 구성하는 인접 리스트를 구현하고, 리스트를 생성한 뒤 DFS를 수행하였다.
• DFS를 수행할 때, 방문 여부를 기록하는 boolean 배열을 두고, 이 배열 값을 통해 아직 탐방하지 않은 정점만 가도록 구현하였다. 이렇게 하는 이유는, 중간에 노드 간 간선이 없는 경우가 있기 때문에 모든 정점을 방문하기 위한 조치이다.