[백준 BOJ/Silver II] 4963번 : 섬의 개수

 

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

4963번: 섬의 개수

import java.util.Scanner;

public class Main {

    static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
    static int result; // 결과
    static int w; // 너비, j
    static  int h; // 높이, i
    static int[][] map; // 지도

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(true) {
            result = 0;

            w = sc.nextInt();
            h = sc.nextInt();
            map = new int[h][w];

            if (w == 0 & h == 0) break; // 0 0 나오면 종료

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

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

    }

    static void dfs(int x, int y) {
        map[x][y] = 0;

        for(int i=0; i<8; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX>=0 && nextX < h && nextY>=0 && nextY < w) {
                if(map[nextX][nextY] == 1) {
                    dfs(nextX, nextY);
                }
            }
        }


    }
}

 

이번 문제는 대각선까지 포함하기 때문에 확인해야할 부분이 더 늘어난다

그려서 확인해보면 이렇고 이걸 dx, dy로 넣어서 다음 x와 y를 계산해주면 된다

이어지는것들을 모두 타고타고가며 확인해주고, 돌아온 후 다음 범위로 넘어가며 답을 더해주면 완성!