백준 4963번 - 섬의 개수(DFS)

 

 

▶코드

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

public class Main {
    static int range[][];
    static boolean visited[][];
    static int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
    static int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
    static int W, H;
    static int cnt;
    static LinkedList<Integer> result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        cnt = 1;
        while (true) {
            st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            if (W == 0 && H == 0)
                break;

            range = new int[H][W];
            visited = new boolean[H][W];
            result = new LinkedList<>();
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    range[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (range[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j);
                        result.add(cnt);
                        cnt = 1;
                    }
                }
            }
            System.out.println(result.size());
        }

    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 8; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && ny >= 0 && nx < H && ny < W && !visited[nx][ny] && range[nx][ny] == 1) {
                dfs(nx, ny);
                cnt++;
            }
        }
    }
}