-
[BOJ - JAVA] 4963 - 섬의 개수 (BFS) 본문
# 주소
https://www.acmicpc.net/problem/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로 바꾸어 주면 방문했다는 뜻이 되므로 다시는 방문하지 않을 것입니다.
이해가셨나요??
정말 쉽죠?
감사합니다.
'백준 문제 풀이' 카테고리의 다른 글
[BOJ - JAVA] 15686 - 치킨 배달 (완전 탐색, 백트래킹) (0) | 2021.12.07 |
---|---|
[BOJ - JAVA] 2468 - 안전 영역 (DFS) (0) | 2021.12.06 |
[BOJ - JAVA] 11724 - 연결 요소의 개수 (BFS) (0) | 2021.12.04 |
[BOJ - JAVA] 10814 - 나이순정렬(Comparator, Comparable 인터페이스) (0) | 2021.12.03 |
[BOJ - JAVA] 1021 - 회전하는 큐 (덱) (0) | 2021.11.28 |