[SWEA / 창용 마을 무리의 개수 / JAVA / DFS]

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

SW Expert Academy

 

 

문제 접근

정수형 배열 타입의 List 생성해서 마을 내의 아는 사람들 끼리 서로서로 리스트에 번호를 추가시켜준다.

ex)1, 2, 5가 아는 사이일 경우 list[1] = {2, 5}, list[2] = {1,5}, list[5] = {1,2} 처럼 저장될 것이다.

 

여기서 1부터 방문 탐색을 진행

방문하지 않은 번호면 방문후 true로 방문 표시

1번 탐색하러 들어가면 2번은 아직 탐색 전이니까 2번 탐색하러 들어가서 방문 표시

그럼 list[2]의 요소들을 또 탐색했는지 검사, 1은 이미 탐색했으니 다음 5를 탐색

list[5]의 요소들을 탐색하러 들어가면서 쭉 반복한다.

 

이런 식으로 진행하면 연결되어 있는 모든 수 들을 다 탐색하고 더 이상 탐색할 수가 없어서 돌아오면 그룹 숫자 +1이 된다.

제일 처음에 1부터 방문 진행했으니 그 다음 반복문의 숫자로 다시 진행 (2, 5는 이미 방문 체크했으니 바로 continue로 넘어감)

 

이렇게 만들어지는 그룹 수를 파악할 수 있다.

// SWEA

import java.util.*;
import java.io.*;
 
public class Solution {
	
	static int N, M;
	static boolean[] visited;
	static ArrayList<Integer>[] edge;
	
    public static void main(String[] args) throws IOException  {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int T = Integer.parseInt(br.readLine());
    	
    	for(int t=1; t<=T; t++) {
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int answer = 0;
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	visited = new boolean[N+1];
    	edge = new ArrayList[N+1];
    	
    	for(int i=1; i<=N; i++) edge[i] = new ArrayList<Integer>();
    	
    	for(int i=0; i<M; i++) {
    		
    		st = new StringTokenizer(br.readLine());
    		int start = Integer.parseInt(st.nextToken());
    		int end = Integer.parseInt(st.nextToken());
    		
    		edge[start].add(end); // 1, 2번이 서로 알 경우 1번 리스트에 2저장
    		edge[end].add(start); // 2번 리스트에 1저장해서 서로 아는 사이라는 걸 인지
    	}
    	
    	for(int i=1; i<=N; i++) {
    		if(visited[i]) continue;
    		dfs(i);
    		answer++;
    	}
    	
    	System.out.println("#"+ t+" "+ answer);
    	}
    }
    
    public static void dfs(int num) {
    	visited[num] = true;
    	
    	for(int nextNum : edge[num]) { // 1, 2, 5가 연결됐을 경우 1,2,5 순차적으로 방문표시 해주기, 끝까지 가서 돌아오면 그룹 횟수 +1
    		if(visited[nextNum]) continue;
    		dfs(nextNum);
    	}
    }
}