4963 섬의 개수 (JAVA)

• 8방향으로 DFS를 뻗어 나가야하는 문제
• 인접행렬로 구현
• 배열의 행과 열의 크기가 같지 않기 때문에, 가로 세로 변수를 잘못 넣거나 비교하면 오랜시간 삽질할 수 있으니 주의!

import java.util.*;

/* 4963 섬의 개수 */
public class Main {

    static int w,h, result=0;
    static int[][] graph;
    static boolean[][] ch;
    
    // 8방향 탐색
    static int[] dx = {-1,-1,-1,0,0,1,1,1};
    static int[] dy = {-1,0,1,-1,1,-1,0,1};

	// DFS
    static void DFS(int y, int x){
        ch[y][x] = true;
        for(int i=0; i<dx.length; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >=0 && ny >= 0 &&
               nx < w && ny < h &&
               !ch[ny][nx] && graph[ny][nx]==1)
                    DFS(ny,nx);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            w = sc.nextInt();
            h = sc.nextInt();
            if(w == 0 && h == 0)	// 0,0 입력시 종료
                break;
                
			// 체크배열과 결과값이 static이므로 반복문마다 다시 초기화
            ch = new boolean[50][50];	
            result = 0;

			// w가 가로 h가 높이, 배열엔 [h][w]로 넣어야함을 주의!
            graph = new int[h][w];
            for (int i = 0; i < h; ++i)
                for (int j = 0; j < w; ++j)
                    graph[i][j] = sc.nextInt();

            for (int i = 0; i < h; ++i)
                for (int j = 0; j < w; ++j) {
                    if (!ch[i][j] && graph[i][j] == 1) {
                        DFS(i, j);
                        result++;
                    }
                }
            System.out.println(result);
        }
    }
}