백준 - 4963

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

public class Main {
    static int[][] dir = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
    };
    static int h, w;
    static boolean[][] island;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String a = "";
        while (!(a = br.readLine()).equals("0 0")) {
            String[] s = a.split(" ");
            w = Integer.parseInt(s[0]);
            h = Integer.parseInt(s[1]);

            island = new boolean[h][w];
            visited = new boolean[h][w];

            for (int i = 0; i < h; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    int num = Integer.parseInt(st.nextToken());
                    if (num == 1) island[i][j] = true;
                }
            }
            int cnt = 0;
            for(int i = 0; i < h; i++){
                for(int j = 0; j < w; j++){
                    if(island[i][j] && !visited[i][j]){
                        dfs(i,j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }
    static void dfs(int r, int c){
        visited[r][c] = true;

        for(int d = 0; d < 8; d++){
            int nr = r+ dir[d][0];
            int nc = c + dir[d][1];

            if(nr >= 0 && nc >= 0 && nr < h && nc < w
            &&!visited[nr][nc] && island[nr][nc]){
                dfs(nr,nc);
            }
        }
    }
}

풀이과정 및 리뷰

1. 0 0 이 들어오면 종료되므로,

   String a = ""; while (!(a = br.readLine()).equals("0 0") 로 조건 만족시 반복문 안 돌도록

2. 처음 2차원 배열 섬 입력을 받을때 1인 경우 true로 받는 boolean[][] island 생성 및 초기화

3. 대각선으로 이어져있어도 섬으로 인정되므로 8방탐색 배열 선언

4. 이미 방문한 곳을 제외하기 위한 boolean[][] visited 생성 및 초기화

5. 처음 dfs내부에서 섬 개수를 count 로 받아 매 호출마다 ++ 하려고 했지만, 디버깅이 어렵고 흐름따라가기가 어려워 아예 메인함수로 빼버림

6. DFS

• 일단 시작점 visited = true 로 변경 후, 인접 8방향 탐색 시작
• 배열을 벗어나지 않음 && 방문한적 없음 && 섬인 경우 재귀호출
• 종료조건 : 배열을 벗어나거나, 방문한 노드거나, 섬이 아닌 경우

1. dfs의 재귀호출이 종료되면, 메인함수 내부에서 루프를 돌며 섬인 경우 && 방문하지 않은 경우에 해당하는

   노드를 찾아 dfs를 재호출

→ 이때, dfs가 호출되고 연결된 지점이 없어 메서드가 종료되면 count가 올라가는 식으로 로직을 짬

보완점

1. null 체크 → 해당 문제는 해당없음

• while (!(a = br.readLine()).equals("0 0"))
• 입력이 "0 0"이면 종료하도록 잘 처리했는데, 만약 입력이 없거나 파일 끝(EOF)일 때 br.readLine()이 null이 될 수 있습니다. null 체크도 넣으면 더 안정적입니다.

1. 방문 체크 시점

• visited[r][c] = true;는 dfs 초반에 해주셨는데, 중복 방문을 막기 위해 dfs 호출 직전에 하는 것도 안전합니다.