백준 4963 - 섬의 개수 (JAVA 자바)

백준 4963 - 섬의 개수 (JAVA 자바)

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

DFS인데 다른 문제들과는 다르게 8방향을 모두 봐야합니다.

(상하좌우 + 각 대각선)

그 부분만 주의해서 코딩하시면 됩니다.

어려운 문제는 아니었습니다.

 

아! 그리고 while문을 사용해서

0 0 이 들어올때까지 돌려줘야됩니다. (입력의 마지막줄에 0이 두개 들어옴)

자세한 내용은 코드를 참고해주세요~

 

 

 

 

import java.util.*;
 
public class Main {
 
    static int w,h,cnt;
    static int map[][];
    static boolean visits[][];
    static int dx[] = {1,-1,0,0,1,1,-1,-1};
    static int dy[] = {0,0,1,-1,1,-1,1,-1};
    
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        
        while(true) {
            
            h = sc.nextInt();
            w = sc.nextInt();
            
            if (w == 0 && h == 0) {
                break;
            }
            
            cnt = 0;
            
            map = new int [w+2][h+2];
            visits = new boolean [w+2][h+2];
            for(int i=1; i<=w; i++) {
                for(int j=1; j<=h; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            
            
            for(int i=1; i<=w; i++) {
                for(int j=1; j<=h; j++) {
                    if(!visits[i][j] && map[i][j]==1) {
                        dfs(i,j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
 
    }
    
    private static void dfs(int x, int y) {
        visits[x][y] = true;
        
        for(int i=0; i<8; i++) {
            int new_x = x+dx[i];
            int new_y = y+dy[i];
            if(!visits[new_x][new_y] && map[new_x][new_y] == 1) {
                dfs(new_x, new_y);
            }
        }
    }
    
}