[백준 알고리즘] Q10216 Count Circle Groups -BFS 너비탐색

1. Java 구현

           
package stream;

import java.io.*;
import java.util.*;
import java.util.concurrent.ConcurrentLinkedQueue;
public class Main {

	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int  t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++) {
        	int  n = Integer.parseInt(br.readLine());
            List points = new ArrayList<>();
        	for(int j = 0; j < n; j++) {
        		String[] input = br.readLine().split(" ");
        		points.add(new Main().new Point(Integer.parseInt(input[0]), 
                           Integer.parseInt(input[1]), Integer.parseInt(input[2])));
        	}
        	
        	boolean[] visited = new boolean[points.size()];
        	int cnt = 0;
        	for(int j = 0; j < points.size(); j++) {
        		if(!visited[j]) {
        			visited[j] = true;
        			bfs(points, j, visited);
        			cnt++;
        		}
        	}
        	sb.append(cnt + "\n");  
        }
        bw.write(sb.toString());
        bw.close();
	}
	
	public static void bfs(List points, int index, boolean[] visited) {
		Queue temp = new ConcurrentLinkedQueue<>();
		temp.add(points.get(index));
		
		while(!temp.isEmpty()) {
			Point standard = temp.poll();
			for(int i = 0; i < points.size(); i++) {
				if(!visited[i] && standard.isContinous(points.get(i))) {
					visited[i] = true;
					temp.add(points.get(i));
				}
			}
		}
	}
	
	public class Point {
		private int x;
		private int y;
		private int r;
		
		public Point(int x, int y , int r) {
			this.x = x;
			this.y = y;
			this.r = r;
		}
		
		public boolean isContinous(Point point) {
			return Math.sqrt(Math.pow(this.x - point.x, 2) + Math.pow(this.y - point.y, 2)) <= this.r +point.r;
		}
	}
}

2. 코드설명

 이 문제는 BFS 너비탐색 알고리즘으로 풀이가 가능한 문제이다. BFS 너비탐색 알고리즘은 기준 노드 기점으로 인접한 노드들을 확인하는 방식으로서,

 더이상 인접한 노드가 존재하지 않을 때까지 계속 반복하는 방식으로 동작한다. 만약 설명이 어렵다고 느낀다면, 아래 문제를 먼저 풀어보는 것을 추천한다.

  백준 알고리즘 Q2606 바이러스 문제 해설 : https://lkhlkh23.tistory.com/53

 이 문제를 풀때 중요한 포인트 2가지가 있다. 첫번째는 두 지점이 서로 인접한지를 체크하는 것이다. 처음에 문제를 풀었을 때, 2차원 평면에서 상, 하, 좌, 우

 인접하면 두 지점은 인접하겠다고 착각을 했다. 이 문제에서 인접이라고 하면 아래와 같은 사진을 의미한다.

 지점을 기준으로 거리만큼의 원이 있고, 두원의 반지름의 합이 두점의 거리보다 크면 두 지점은 인접한 지점이다. 

 두번째로 체크해야 할 것은 방문유무를 확인하는 boolean 타입의 1차원 배열이다. 방문유무를 체크하는 것은 BFS 너비탐색 알고리즘에서 정말 중요하다.

 이미 확인했다는 것은, 결국은 더이상 확인할 필요가 없다는 뜻이기 때문에 속도 측면에서 정말 필요하다.

 방문유무를 확인하지 않아도 답은 분명 나올 것이다. 그렇지만, 방문유무를 확인하지 않으면 시간초과가 나온다. 경험했다. 반드시 체크하자!

3. Pain Point

 문제에서 말하는 인접함을 착각했기 때문에 정말 시간이 오래 걸렸다. 처음부터 내가 잘못 파악했다는 사실도 모르고 계속 시간낭비를 했다.

 BFS 너비탐색 알고리즘이라는 사실을 알았기 때문에, 비슷한 문제들과 착각을 해서 요구사항을 명확히 파악하지 못했던 것 같다!

 크리스마스때 아침에 일어나자마자 이 문제를 풀고 맞춰서 좋아하는 내 모습을 보니 뭔가 짠했다. 눈이 촉촉하다. 뭔가가 흘러내린다.

 나는 괜...차...ㄴ...타.... 행..보..ㄱ..하..ㄷ..ㅏ...