[백준 / Java] 4963 섬의 개수

문제 정보

• 난이도: 실버 1
• 태그: 그래프, DFS, BFS

풀이

1. 이중 포문을 돌면서 모든 격자를 검사한다.
2. m[i][j]의 값이 0이거나(바다를 의미), 이미 방문이 된 격자라면 넘어간다.
3. 육지이면서 처음 방문한 격자라면 그 좌표에서 dfs를 시작한다. (bfs도 가능하다.)
4. dy, dx 배열을 통해서 상, 하, 좌, 우, 대각선으로 인접한 칸을 모두 검사하고, 만약 visited 값이 false이면서 육지이면 그 칸에서 dfs를 다시 호출하는 식으로 탐색한다.

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

5. 이중 포문을 빠져나왔을 때, dfs가 실행된 횟수가 섬의 개수가 된다.

import java.util.Scanner;

public class Main {
    static boolean[][] visited = new boolean[51][51];
    static int[][] m = new int[51][51];

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

    static int w, h;

    static boolean is_safe(int y, int x) {
        if(y <= h && y >= 1 && x <= w && x >= 1) return true;

        return false;
    }

    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        int ans = 0;

        while(true) {
            w = sc.nextInt(); // 가로
            h = sc.nextInt(); // 세로
            if(w == 0 && h == 0) break;

            // 초기화
            for(int i=0; i<51; ++i) {
                for(int j=0; j<51; ++j) {
                    visited[i][j] = false;
                }
            }

            for(int i=1; i<=h; ++i) {
                for(int j=1; j<=w; ++j) {
                    m[i][j] = sc.nextInt();
                }
            }

            ans = 0;
            for(int i=1; i<=h; ++i) {
                for(int j=1; j<=w; ++j) {
                    if(m[i][j] == 0 || visited[i][j] == true) continue;

                    dfs(i, j);
                    ans += 1;
                }
            }

            System.out.println(ans);
        }

    }

    public static void dfs(int y, int x) {
        visited[y][x] = true;

        for(int i=0; i<8; ++i) {
            int ny = y + dy[i], nx = x + dx[i];

            if(!is_safe(ny, nx)) continue;
            if(visited[ny][nx]) continue;
            if(m[ny][nx] == 0) continue;

            dfs(ny, nx);
        }
    }
}