[백준] 4963 섬의 개수 - Java

 

 

 

지난번에 풀었던 유기농 배추와 유사한 문제이다.

 

매 테스트케이스마다 지도와 방문 여부, 정답 변수를 초기화 해 주고 dfs를 돌려 탐색하자.

 

 

import java.util.*;
import java.io.*;

public class Main {

    static int N;    
    static int M;
    static int map[][];
        
    static boolean[][] visit;    
    static int cnt;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        while(true){
            st = new StringTokenizer(br.readLine());

            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());

            if(M ==0 && N == 0){
                break;
            }

            map = new int[N][M];
            visit = new boolean[N][M];
            cnt = 0;

            for(int i=0; i<N; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<M; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(!visit[i][j] && map[i][j] == 1){
                        dfs(i,j);
                        cnt++;
                    }
                }
            }

            sb.append(cnt + "\n");
            
            
        }
        System.out.print(sb);

        
    }

    static void dfs(int r, int c){
        visit[r][c] = true;
        for(int i=0; i<8; i++){
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];

            if(nr < 0 || nr >= N || nc < 0 || nc >= M){
                continue;
            }
            if(map[nr][nc] == 0){
                continue;
            }
            if(visit[nr][nc]){
                continue;
            }
            dfs(nr,nc);
        }
    }
}