[백준 Java] 4963 섬의 개수

📚 문제  

4963번: 섬의 개수

🔍 아이디어  

기본적인 구현 문제이다.

DFS/ BFS 두 가지로 모두 풀 수 있지만 나는 BFS를 이용해서 풀이하였다.

갈 수 있는 길이 대각선을 포함함으로 경로에 추가한다. 또한 모든 섬을 찾아야 하기에 모든 배열을 탐색하면서 이미 방문하지 않은 섬의 경우에 탐색을 시작하고 해당섬을 BFS로 순회하면서 visit 배열을 색칠하면 된다.(방문처리를 한다)

 

즉, 모든 지도를 탐색하면서 1번 섬을 만난 경우 1번 섬에 대해 visit을 모두 칠하고, 2번 섬을 만난 경우 2번 섬의 영역에 대한 visit을 모두 방문처리 하면서 모든 섬의 개수를 구하면 된다.

 

📝 풀이 

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

public class Main{
    private static int w, h;
    private static int[][] map;
    private static boolean[][] visited;
    private static final Queue<int[]> queue = new LinkedList<>();
    private static final int[][] dirs = {{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());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            if (w == 0 && h == 0) break;
            map = new int[h][w];
            visited = new boolean[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());
                }
            }
            sb.append(findLands()).append("\n");

        }
        System.out.println(sb);
    }

    public static int findLands() { //모든 섬 탐색
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    coloredLands(new int[]{i, j});
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private static void coloredLands(int[] point) { //한 섬을 만난경우 나머지 섬의 영역 방문처리
        visited[point[0]][point[1]] = true;
        queue.add(point);

        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            for (int[] dir : dirs) {
                int mvX = p[0] + dir[0];
                int mvY = p[1] + dir[1];
                if (mvY < 0 || mvX < 0 || h <= mvX || w <= mvY || visited[mvX][mvY] || map[mvX][mvY] == 0) continue;
                visited[mvX][mvY] = true;
                queue.add(new int[]{mvX, mvY});
            }
        }
    }

}