[☁️ 구름톤 챌린지] 4주차 학습일지 - 1

문제 16. 연합

전형적인 BFS 문제이다. 

이 문제는 BFS에서 queue에 이 다음에 방문할 값을 넣을 때하는 방문 체크에서, 이 다음 값을 방문했는지 확인하는 것이 아닌 현재 값을 방문했는지 계속 확인하는 바람에 틀렸다. 

방문 체크하는 값을 바꾸어주니 통과되는 것을 확인할 수 있었다.

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

class Main {
	static int N, M;
	static int[][] map;
	static boolean[] visited;
	static int result;
	static Queue<Integer> queue;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		
		queue = new LinkedList();
		map = new int[N+1][N+1];
		visited = new boolean[N+1];
		result = 1;
        
		for(int i = 0; i < M; i++) {
			str = br.readLine().split(" ");
			int y = Integer.parseInt(str[0]);
			int x = Integer.parseInt(str[1]);
			map[y][x] = 1;
		}
		
		for(int i = 1; i <= N; i++) {
			if(!visited[i]) {
				queue.add(i);
				result++;
			}
			
			while(!queue.isEmpty()) {
				int now = queue.poll();
				visited[now] = true;
				for(int next = 1; next <= N; next++) {
					if(!visited[next] && 
						map[now][next] == 1 && 
						map[next][now] == 1) {
						queue.add(next);
					}
				}
			}
		}
		System.out.println(result-1);
	}
}

 

문제 17. 통신망 분석

이 문제 역시 BFS로 풀이할 수 있다. 다만 비교하는 조건이 까다로워, 문제 풀이가 복잡했다. 

먼저 컴포넌트를 찾기 위해 다음 정보가 필요하다.

1. 컴포넌트에 속한 컴퓨터의 수

2. 컴포넌트에 속한 통신 회선의 수

3. 컴포넌트에서 가장 작은 컴퓨터의 번호

 

Pair 클래스 -> 컴포넌트를 관리하는 클래스

컴포넌트에 있는 컴퓨터 정보(list)와 밀도(value)를 갖는다.

static class Pair {
	List<Integer> list;
	double value;
		
	Pair(List<Integer> list, double value) {
		this.list = list;
		this.value = value;
	}
}

방문 지점마다 bfs로 해당 컴포넌트의 컴퓨터 리스트와 value를 계산한다. 오름차순으로 정렬한다.

bfs로 계산하여 반환된 Pair 클래스에서 value 값을 비교해가면서 값을 갱신한다.

	public static Pair bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		
		Set<Integer> component = new HashSet<>();
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			// 방문했다면
			if(visited[now]) {
				continue;
			}
			
			// 방문 표시
			visited[now] = true;
			component.add(now);
			
			for(int to : graph[now]) {
				if(!visited[to]) {
					q.add(to);
				}
			}
		}
		
		int edge = 0;
		
		for (int i : component) {
			for (int to : graph[i]) {
				if (component.contains(to)) {
					edge++;
				}
			}
		}
		
		List<Integer> sortedList = new ArrayList<>(component);
		Collections.sort(sortedList);
		
		return new Pair(sortedList, (double) edge / component.size());
	}

 

전체 코드

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

class Main {
	static int N, M;
	static List<Integer>[] graph;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		
		graph = new ArrayList[N+1];
		
		for(int i = 0; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		
		visited = new boolean[N+1];
			
		for(int i = 0; i < M; i++) {
			str = br.readLine().split(" ");
			int y = Integer.parseInt(str[0]);
			int x = Integer.parseInt(str[1]);
			graph[y].add(x);
			graph[x].add(y);
		}
		
		List<Integer> result = new ArrayList<>();
		double density = 0;
		
		for(int i = 1; i <= N; i++) {
			if(!visited[i]) {
				Pair pair = bfs(i);
				List<Integer> temp = pair.list;
				double tempDensity = pair.value;
				
				if (Math.abs(tempDensity - density) < 1e-8) {
					if (result.size() > temp.size()) {
						result = temp;
						density = tempDensity;
					} else if (result.size() == temp.size()) {
						if (temp.get(0) < result.get(0)) {
							result = temp;
							density = tempDensity;
						}
					}
				} else if (tempDensity > density) {
					result = temp;
					density = tempDensity;
				}
			}
		}
		
		for (int node : result) {
			System.out.print(node + " ");
		}
	}
	
	public static Pair bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		
		Set<Integer> component = new HashSet<>();
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			// 방문했다면
			if(visited[now]) {
				continue;
			}
			
			// 방문 표시
			visited[now] = true;
			component.add(now);
			
			for(int to : graph[now]) {
				if(!visited[to]) {
					q.add(to);
				}
			}
		}
		
		int edge = 0;
		
		for (int i : component) {
			for (int to : graph[i]) {
				if (component.contains(to)) {
					edge++;
				}
			}
		}
		
		List<Integer> sortedList = new ArrayList<>(component);
		Collections.sort(sortedList);
		
		return new Pair(sortedList, (double) edge / component.size());
	}
	
	static class Pair {
		List<Integer> list;
		double value;
		
		Pair(List<Integer> list, double value) {
			this.list = list;
			this.value = value;
		}
	}
}