[JAVA] SWEA 7465 창용 마을의 무리의 갯수

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

SW Expert Academy

---

풀이 방법

입력 예제 중

6 5
1 2
2 5
5 1
3 4
4 6 를 그림으로 간단하게 나타보면 

이렇게 표현할 수 있다. 1번 사람은 2,5번과 알고 있고(양방향이므로 5번도 알고 있음), 2번~6번도 예제와 마찬가지이다. 그래서 무리는 2개가 만들어지는 것을 알 수 있다. 

전형적인 DFS문제로, 각 번호와 연결된 사람들을 끝까지 파고들다보면 무리가 하나씩 형성되는 것을 알 수 있다! 

그림과 똑같이 풀기 위해 인접리스트를 만들어, 각 번호와 연결된 사람들을 탐색했다.

 

JAVA 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA_7466_창용마을무리의개수 {
	
	static StringTokenizer st;
	static StringBuilder sb=new StringBuilder();
	static int N,M;
	static boolean visited[];
	static ArrayList<ArrayList<Integer>> input;
	static int cnt;
	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+1; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			input=new ArrayList<ArrayList<Integer>>();
			for (int i = 0; i < N+1; i++) {
				input.add(i, new ArrayList<Integer>());
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int len= st.countTokens();
				int x=Integer.parseInt(st.nextToken());
				if(len==2) {
					int y=Integer.parseInt(st.nextToken());
					// 양방향 그래프
					input.get(x).add(y);
					input.get(y).add(x);
					continue;
				}
				input.get(x).add(x);
			}
			
			visited=new boolean[N+1];
			
			cnt=0;
			for (int i = 1; i < N+1; i++) {
				if(dfs(i)) cnt++;
			}
			sb.append("#").append(t).append(" ").append(cnt).append("\n");
		}
		System.out.println(sb);
	}
	
	private static boolean dfs(int i) {
		if(!visited[i]) {
			visited[i]=true;
			for (int j = 0; j < input.get(i).size(); j++) {
				if(!visited[input.get(i).get(j)]) {
					dfs(input.get(i).get(j));
				}
			}
			return true;
		}

		return false;
	}
}

처음에 양방향 그래프인줄 모르고 4번이나 틀렸다가 문제를 다시 읽어보니 양방향 그래프였다..ㅎ