[백준] 4963 섬의 개수 - Java

문제 - 섬의 개수

https://www.acmicpc.net/problem/4963

 

 

 

 

접근 방법

 

이 문제도 그래프 완전 탐색이다 즉, bfs와 dfs로 풀 수 있는 문제이다

하지만 이 문제가 다른 점은 대각선에 있는 것도 탐색을 해야 한다는 것이다 

이 부분만 잘 구현 하면 될 것 같다

 

---

코드 작성

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, -1, 0, 1, -1, 1, -1, 1};
    static int[] dy = {1, 0, -1, 0, 1, 1, -1, -1};
    static int count;

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

            String str = "";
            StringBuilder sb = new StringBuilder();
            while (!(str = br.readLine()).equals("0 0")) {
                st = new StringTokenizer(str);

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

                map = new int[M][N];
                visited = new boolean[M][N];

                for (int i = 0; i < M; i++) {
                    st = new StringTokenizer(br.readLine());

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

                int count = 0;

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

                sb.append(count).append("\n");
            }
            System.out.println(sb);
        }

    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 8; i++) {
            int ix = dx[i] + x;
            int iy = dy[i] + y;

            if (ix >= 0 && ix < M && iy >= 0 && iy < N) {
                if (!visited[ix][iy] && map[ix][iy] == 1) {
                    dfs(ix, iy);
                }
            }
        }
    }
}