[BOJ - JAVA] 2667 - 단지번호 붙이기(BFS)

# 주소

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

# 문제

# 문제해설 및 코드 리뷰

package first;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	public static int n;
	public static int arr[][];
	public static boolean visit[][];
	public static ArrayList<Integer> list = new ArrayList<>();
	public static Queue<Point> queue = new LinkedList<>();
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int count = 0;
		n = scan.nextInt();
		arr = new int[n][n];
		visit = new boolean[n][n];
		for(int i = 0; i < n; i++) {
			String str = scan.next();
			for(int j = 0; j < n; j++) {
				arr[i][j] = str.charAt(j) - 48;
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(arr[i][j] == 1 && visit[i][j] == false) {
					bfs(i,j);
					count++;
				}
			}
		}
		System.out.println(count);
		Collections.sort(list);
		for(int i = 0; i < list.size(); i++)
			System.out.println(list.get(i));
	}
	public static void bfs(int i, int j) {
		int nx, ny;
		int ans = 1;
		queue.offer(new Point(i,j));
		visit[i][j] = true;
		while(queue.isEmpty() == false) {
			Point now;
			now = queue.poll();
			for(int k = 0; k < 4; k++) {
				nx = now.x + dx[k];
				ny = now.y + dy[k];
				if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
					if(arr[nx][ny] == 1 && visit[nx][ny] == false) {
						queue.offer(new Point(nx, ny));
						visit[nx][ny] = true;
						ans++;
					}
				}
			}
		}
		list.add(ans);
	}
}

이번에도 BFS 문제를 가져왔습니다. n x n 배열이기 때문에 n을 입력받습니다.

그리고 boolean타입의 visit을 2차원으로 선언해주는데, 이것은 방문하지 않은 값에 한해서만 방문해야하기 때문입니다.

또한 입력받는 arr배열들이 띄어쓰기가 안된채로 입력되므로 처음에 각 줄마다 String 타입으로 입력받고 그것을 str.charAt(j) - 48이라고 쓰게되면 컴파일할 때 각 문자로 인식해서 arr에 들어갑니다..!! 

-48이라고 해도 좋고, - '0' 둘 다 어느 것이든 괜찮습니다.

이후 이중 for문으로 방문하지 않은 bfs에 대해 count를 증가시켜주는데요. 여기서 count는 각 bfs너비의 크기를 의미합니다. 무슨 의미냐면, 이중 for문의 if문에서 arr[i][j] == 1이고 visit[i][j] == false란 것은 bfs를 한 번 실행하고 나면, 주변의 모든 방문할 수 있는 인덱스는 true로 바뀔 것이기 때문에 visit이 false가 되어야만 영역의 개수를 구할 수 있다는 의미가 됩니다. 그러므로 각 영역에서 false인 곳이면서 arr가 1이라면 bfs를 실행할 수 있다는 것이고, 각 영역의 개수가 위의 예제처럼 입력된다면 count 는 3이 될 것입니다. 이후, bfs내부의 구조를 살펴보겠습니다.

bfs내부를 살펴보면, 입력받은 int i, int j를 인자로 가지는 것을 확인할 수 있습니다.

그리고 nx, ny를 선언하고 영역의 크기 ans를 1로 선언하겠습니다.

queue를 우리는 Point타입으로 선언했기 때문에, queue에는 int타입의 점이 저장됩니다.

그리고 이것을 사용하기 위해선, 반드시 java.awt.Point를 선언해주어야 사용이 가능합니다.

또한 queue.add(new Point(i,j))로 바로 데이터를 삽입 가능하여 사용하기 편리하고 주의해야할 부분이 하나 있는데, queue.poll() 하게 되면 데이터가 모두 삭제되므로 queue.peek().x로 값을 뽑아낸 뒤 queue.poll()을 사용하는 것을 추천드립니다. 

이 java.awt.Point는 java platform에서 public class인 Point class는 Point2D를 상속받고, Serializable을 implements하는 클래스라고 합니다. 따라서 좌표 값을 사용할 때 사용해주면 상당히 편리합니다.

다시 bfs내부 구조로 들어가서, queue에 (i,j)를 삽입해봅시다. 그리고 들어간 visit은 true로 바꾸어 주고 while문으로 들어가 queue가 빌 때까지 계속해서 실행합니다. bfs로 미로찾기, 너비, 영역 구하는 문제는 무조건 queue에 담고 그 queue가 빌때까지 계속 실행했던 것 기억하시죠??

queue의 점 하나를 now라고 선언하고 그 now를 queue.poll()하여 가져옵니다. 이후 정적 변수로 담아두었던 dx,dy를 이용할텐데, 이 dx,dy는 순서대로 상,우,하,좌 의 방향을 의미합니다. 따라서 bfs내부 구조에서 제일 처음 선언했던 nx,ny를 뽑아낸 queue의 now의 x점과 y점에 담습니다. 

그리고 if문에 nx,ny가 모두 0보다 크거나 같고 n보다 작은 범위 안에서, 또 방문하지 않은 visit값과 그 arr가 1일 때 새로운 point를 다시 queue에 담습니다. 그리고 visit을 true로 바꾸어주고 ans의 크기(영역의 크기)를 증가시켜주면 어느 한 영역의 크기가 구해지는 것입니다.

위의 예제처럼 실행할 경우 영역이 총 3개이기 때문에 총 count는 3개가 나오고 그 ans를 list에 담아 출력하면 정답이 되는 것입니다. 

여기서 왜 굳이, list를 썼는지 혹시 궁금하실까봐 정리해드리겠습니다.

list는 ArrayList타입인데, ArrayList는 배열의 크기가 가변적이라는 특징이 있습니다. 즉, 굳이 배열의 크기를 지정해주지 않아도 들어가는 값에 따라서 크기가 달라질 수 있다는 장점이 있죠!! 그래서 코테에서 arraylist를 사용하면 편리한 것입니다. 그러므로 list에 값을 넣은 후 그것을 오름차순으로 정리해주는데, arraylist의 오름차순은 Collections.sort(list)만 입력해주면 알아서 정렬됩니다!! 이것을 for문으로 출력해주면 원하는 값을 얻으실 수 있습니다.

감사합니다.