구름톤 챌린지[JAVA] 16일 차 학습 일기

구름톤 챌린지 연합

 

[느낀점]

쉬운문제인줄알았는데 생각보다 어려워서 풀이를 참고했다. 지금까지 풀었던 문제인 큐에 담아 탐색하는 문제이다. 이번 주 구름톤 챌린지는 그래프 문제인데 그래프 문제는 자신이없어서 큰일이다. 풀이를 최소한으로 참고하면서 풀어 볼 예정이다.

 

[결과 코드]

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		boolean[][] bridges = new boolean[N+1][N+1];
		boolean[] visited = new boolean[N+1];//default == false
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			bridges[s][e] = true;
		}
		int count = 0;
		for(int i=1;i<=N;i++){
			if(visited[i]==false){
			Queue<Integer> q = new LinkedList<>();
			q.add(i);
			
			while(!q.isEmpty()){
				int currentNode = q.poll();
				visited[currentNode] = true;
				
				for(int nextNode=1;nextNode<=N;nextNode++){
					if(bridges[currentNode][nextNode] == true && 
						 bridges[nextNode][currentNode] == true && 
						 visited[nextNode] == false){
						q.add(nextNode);
					}
				}
			}
			count++;
		}
		}
		System.out.println(count);
	}
}