<Algorithm> 72. 4963번 섬의 개수(DFS)

1. 4963번 섬의 개수

• 기본 DFS 문제, 처음으로 테스트 케이스 확인 없이 한번에 맞춘 문제, DFS로 영역 구하는 문제는 어느정도 이해가 된 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static boolean[][] visited;
    static int count;
    public static void main(String[] args) throws IOException {
        
        ArrayList<Integer> ans = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(;;) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken()); 
            int arr[][] = new int[N][M];
            visited = new boolean[N][M];
            count = 0;
            
            if(N==0&&M==0) break;
            
            
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < M; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(!visited[i][j] && arr[i][j] == 1) {
                        dfs(i, j, N, M, arr);
                        count++;
                    }
                }
            }
            
            ans.add(count);
        }
        
        for(Integer in : ans)
            System.out.println(in);
    
    }
    private static void dfs(int x, int y, int n, int m, int[][] arr) {
        
        int[] dx = {0,0,1,-1,1,-1,1,-1};
        int[] dy = {1,-1,0,0,-1,1,1,-1};
        
        visited[x][y] = true;
        
        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >=0 && ny >=0 && nx < n && ny < m && !visited[nx][ny] && arr[nx][ny] == 1) {
                dfs(nx, ny, n, m, arr);
            }
            
        }
        
    }
}
 

참고 & 출처