구름톤 챌린지 16일차

문제

https://level.goorm.io/exam/195698/%EC%97%B0%ED%95%A9/quiz/1

구름LEVEL

 

풀이

그래프 완전 탐색문제는 BFS, DFS를 사용해야 하는데 BFS가 편하여 BFS를 사용하여 문제를 풀었다.

문제에서 조건은 다음과 같이 주어졌다.

• A섬과 B섬이 있을 때, 서로 이동할 수 있으면 연합이 될 수 있다.
• 연합 안에서 어떤 섬에서 출발해도, 연합의 모든 섬에 방문할 수 있어야 한다.
• 모든 섬은 하나의 연합에 속해있다.

1. visited 배열을 이용하여 섬의 방문여부를 나타내준다.

2. 그래프에서 내가 방문할 노드가 현재 노드에 연결되어 있는지 확인하고 마찬가지로 현재노드가 방문할 노드에 연결되어 있는지 확인해준다.

 

이때 2번에서 list의 contains() 를 이용하여 노드가 연결되어 있는지 확인할 수 있지만 이차원배열을 이용하여 확인할 수도 있다.  이차원배열을 이용한다면 시간을 좀 더 줄일 수 있다.

 

코드

list의 contains()을 사용하여 푼 풀이

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

class Main {
	static List<Integer> arr [];
	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());
		
		arr = new LinkedList [n+1];
		
		for(int i=0;i<=n;i++){
			arr[i] = new LinkedList<>();
		}
		
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine());
		
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			arr[s].add(e);
		}
		
		int result = bfs(n);
		System.out.println(result);
	}
	
	static int bfs(int n){
		boolean visited [] = new boolean [n+1];
		Queue<Integer> que = new LinkedList<>();
		
		int result = 0;
		for(int i=1;i<=n;i++){
			if(visited[i]) continue;
			que.add(i);
			result++;
			while(!que.isEmpty()){
				int pos = que.poll();
				for(int j=0;j<arr[pos].size();j++){
					int next = arr[pos].get(j);
					if(visited[next]) continue;
					if(arr[next].contains(pos)){
						que.add(next);
						visited[next] = true;
					}
					
				}
			}
		}
		
		return result;
	}
}

 

이차원배열을 이용한 풀이

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

class Main {
	static List<Integer> arr [];
	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());
		
		arr = new LinkedList [n+1];
		int check [][] = new int [n+1][n+1];
		
		for(int i=0;i<=n;i++){
			arr[i] = new LinkedList<>();
		}
		
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine());
		
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			arr[s].add(e);
			check[s][e] = 1;
		}
		
		int result = bfs(n, check);
		System.out.println(result);
	}
	
	static int bfs(int n, int [][] check){
		boolean visited [] = new boolean [n+1];
		Queue<Integer> que = new LinkedList<>();
		
		int result = 0;
		for(int i=1;i<=n;i++){
			if(visited[i]) continue;
			que.add(i);
			result++;
			while(!que.isEmpty()){
				int pos = que.poll();
				for(int j=0;j<arr[pos].size();j++){
					int next = arr[pos].get(j);
					if(visited[next]) continue;
					if(check[next][pos]==1){
						que.add(next);
						visited[next] = true;
					}
					
				}
			}
		}
		
		return result;
	}
}