[BOJ - JAVA] 4963 - 섬의 개수 (BFS)

# 주소

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

4963번: 섬의 개수

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	static int[][] arr;
	static int dx[] = {0,1,0,-1,-1,-1,1,1};
	static int dy[] = {1,0,-1,0,-1,1,1,-1};
	static int n,m;
	static boolean[][] visit;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true) {
			n = scan.nextInt();
			m = scan.nextInt();
			if(n == 0 && m == 0) {
				break;
			}
			arr = new int[m][n];
			visit = new boolean[m][n];
			for(int i = 0; i < m; i++) {
				for(int j = 0; j < n; j++) {
					int p = scan.nextInt();
					arr[i][j] = p;
				}
			}
			int count = 0;
			for(int i = 0; i < m; i++) {
				for(int j = 0; j < n; j++) {
					if(!visit[i][j] && arr[i][j] == 1) {
						bfs(i,j);
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
	public static void bfs(int a, int b) {
		Queue<Point> queue = new LinkedList<>();
		queue.offer(new Point(a,b));
		visit[a][b] = true;
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			for(int i = 0; i < 8; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				if(nx >= 0 && ny >= 0 && nx < m && ny < n) {
					if(arr[nx][ny] == 1 && visit[nx][ny] == false){
						queue.offer(new Point(nx,ny));
						visit[nx][ny] = true;
					}
				}
			}
		}
	}
}

풀고도 놀랐습니다. 설마 이렇게 풀어도 되겠어? 했는데 진짜 풀려서요..

이 문제는 대각선도 섬의 개수를 인정을 해주기 때문에 기존의 상,하,좌,우 방향만 생각해줄 것이 아니라 총 8가지 방향에 대해서 고려해야 합니다.

그리고 여기선 미리 테스트 케이스를 주지 않는 것이 특징인데, 잘 보시면 입력문 마지막 줄에 0을 2번 입력할 때 마무리 한다고 되어 있습니다.

그 말인 즉슨, 0 0이 입력되면 입력을 끝마치겠다는 일종의 신호라고 해석할 수 있겠습니다.

단순히 코딩하는 것만이 중요한 것이 아니라 이런 센스도 단박에 알아내는 것이 필요하겠어요

 

while문으로 들어가서 0 0 이 들어오면 break를 걸어주게끔 if문을 짭니다.

그리고 입력받는 p값에 따라 해당하는 이중 for문의 인덱스에 p를 그대로 넣습니다.

그러면 입력 떄 주어졌던 인덱스의 값이 모두 인덱스에 고스란히 저장될 것입니다.

이후 다시 이중 for문을 쓸텐데, 이 때는 꼭 if문을 작성해주셔야 합니다.

첫 째로는 visit == false이어야 하고 두 번째는 arr값이 1이어야 한다는 조건을 꼭 걸어두셔야 합니다.

지금 우리가 푸는 문제는 bfs이기 때문에 0인 값을 탐방할 수는 없잖아요??

1이 입력된 섬의 위치를 탐방하는 것이기 때문에 반드시 위 조건을 달아주셔야 겠습니다.

다시 쭉 내려가서 이 if문을 만족할 때마다 bfs를 실행시킬 건데, bfs가 실행될 때마다 count를 1씩 증가한다고 하면, 고립된 위치인 섬의 위치마다 개수가 증가하게 될 것입니다.

 

그럼 이 bfs문은 어떻게 짤 수 있을까요?

먼저 Queue를 선언할텐데, Point를 제네릭에 받습니다. 이 Queue는 bfs를 푸는데 필수 자료구조니까 기억해주세요.

또한 이 배열은 1차원이 아닌, 2차원이기 때문에 점을 Queue에 저장하기 위해 반드시 Point를 활용해주면 좋습니다.

그래서 queue.offer(new Point(a,b));를 입력하게 되면 queue에 해당 Point가 담기게 되는 것입니다.

더 내려가서 while(!queue.isEmpty())를 보시면 queue문제를 풀 때는 저 구문 없이 코딩하는건 거의 없어요.

왜냐하면 이클립스 같은 툴을 써서 자바를 코딩할 때 저 구문을 안쓰고 queue를 다루면 반드시 오류가 날거에요. queue가 비어있다고... 꼭 안비워져있을때를 달아주어야 합니다.(안그러면 바로 종료되요)

 

그리고 해당 Point now = queue.poll(); 할텐데, 이건 queue에 제일 먼저 들어온 점을 now에 저장한단 뜻입니다.

이렇게 갖고온 now점을 nx와 ny에 각각 더해줄건데, for문으로 들어가셔서 i는 8까지 arr의 nx와 ny를 구합니다.

왜 8이냐면, nx와 ny가 만들어질 수 있는 제일 위에 static으로 선언했던 dx,dy가 각각 8가지씩 있기 때문입니다.

또한 이 nx와 ny는 dx와 dy가 각각 움직여서 생겨난 새로운 위치의 점입니다.

그렇기 때문에 만약 arr[a][b]가 1이었고 방문하지 않은 값이었다면, 주변에 인접한 인덱스의 arr에 대해 똑같이 nx,ny위치로 가서 다시 queue.offer(new Point(nx,ny))를 하고(queue에 새 점을 넣겠다는 뜻 -> 만약 새 점 주변 인덱스가 전부 0이 되면 자동으로 queue에서 삭제) 해당 인덱스의 visit을 true로 바꾸어 주면 방문했다는 뜻이 되므로 다시는 방문하지 않을 것입니다.

이해가셨나요??

정말 쉽죠?

감사합니다.