[BOJ_4963] 섬의 개수(java)

문제

• 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다.
• 섬의 개수를 세는 프로그램 작성
• 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형
• 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어갈 수 있는 경로가 있어야 한다.
• 지도는 바다로 둘러사여 있으며, 지도 밖으로 나갈 수 없다.

어려웠던 점

• 2차원 배열에서 행, 높이 입력
• 입력 마지막 0 0 처리 방법

1. 2차원 배열에서 행, 열 입력

2차원 배열의 행, 열

• 첫 번째 인덱스에 열 선언
• 두 번째 인덱스에 행 선언

2. 종료조건(입력 마지막 0 0) 처리

• 다른 분의 코드 참조했음
• while()문으로 계속 처리하다가 w, h가 0, 0이 된다면 break 처리 0이 된다면 break 처리

while(true){
	st = new StringTokenizer(br.readLine());
	w = Integer.parseInt(st.nextToken());
	h = Integer.parseInt(st.nextToken());

	if(w == 0 && h == 0){
		break;
	}

전체코드

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

public class BOJ_4963 {

    static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};

    static int w; // w : 지도의 너비
    static int h; // h : 지도의 높이
    static int[][] map;
    static int[][] visited;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while(true){
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            if(w == 0 && h == 0){
                break;
            }

            map = new int[h][w];
            visited = new int[h][w];
            count = 0;

            for(int i = 0; i < h; i++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < w; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for(int i = 0; i < h; i++){
                for(int j = 0; j < w; j++){
                    if(map[i][j] == 1 && visited[i][j] == 0){
                        count++;
                        bfs(i,j);
                    }
                }
            }
            System.out.println(count);
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y});
        visited[x][y] = 1;

        while(!queue.isEmpty()){
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for(int i = 0; i < 8; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx < 0 || ny < 0 || nx >= h || ny >= w){
                    continue;
                }
                if(map[nx][ny] == 0 || visited[nx][ny] == 1){
                    continue;
                }
                queue.offer(new int[]{nx,ny});
                visited[nx][ny] = 1;
            }
        }
    }
}

느낀점

• DFS로도 풀어봐야함
• 2차원 배열의 행, 열 입력은 절대 잊으면 안됨