[백준] 4963번 - 섬의 개수 [Java]

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

 

[백준] 4963번 - 섬의 개수 [Java]

[백준] 4963번 - 섬의 개수 [Java]

---

1.  아이디어

 

팔방탐색으로 섬의 개수를 구하는 문제로 BFS와 DFS를 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

BFS, DFS 기본 구현만 하면 바로 해결할 수 있다. 일반적인 사방탐색이 아닌 팔방탐색인 것만 주의하면 된다.

---

3. 코드

 

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

public class Main_BFS {

    private static final int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    private static final int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());

            if (W == 0) break;

            int[][] map = new int[H][W];
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine());

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

            boolean[][] visited = new boolean[H][W];
            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == 0 || visited[i][j]) continue;

                    bfs(i, j, H, W, map, visited);
                    cnt++;
                }
            }

            sb.append(cnt).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void bfs(int r, int c, int H, int W, int[][] map, boolean[][] visited) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{r, c});

        visited[r][c] = true;

        while (!q.isEmpty()) {
            int[] node = q.remove();

            for (int dir = 0; dir < 8; dir++) {
                int nr = node[0] + dr[dir];
                int nc = node[1] + dc[dir];

                if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                if (map[nr][nc] == 0 || visited[nr][nc]) continue;

                q.add(new int[]{nr, nc});
                visited[nr][nc] = true;
            }
        }
    }

}

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

public class Main_DFS {

    private static final int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    private static final int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};

    private static int W;
    private static int H;
    private static int[][] map;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());

            if (W == 0) break;

            map = new int[H][W];
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine());

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

            visited = new boolean[H][W];
            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == 0 || visited[i][j]) continue;

                    dfs(i, j);
                    cnt++;
                }
            }

            sb.append(cnt).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int r, int c) {
        visited[r][c] = true;

        for (int dir = 0; dir < 8; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (map[nr][nc] == 0 || visited[nr][nc]) continue;

            dfs(nr, nc);
        }
    }

}

---

4. 후기

 

- BFS

- DFS