BOJ_4963 : 섬의 개수

👉 문제링크

4963번: 섬의 개수

---

---

🔸 문제 분석 🔸

• h x w 크기의 지도가 주어진다.
  • 1은 땅, 0은 바다이다.
  • 땅은 주변 8방향으로 건너다닐 수 있다.
  • 건너다닐 수 있으면 같은 섬이다.
  • 섬의 개수를 출력한다.
• BFS로 풀이할 수 있다.
  • 지도의 모든 칸을 순회하며 확인한다.
  • 땅을 발견하면 인접한 땅 모두를 체크한다.
  • 체크한 땅은 다시 발견하지 않는다.
  • 체크 횟수를 출력한다.

🔸 코드 🔸

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

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

        int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; //상 상우 우 우하 하 좌하 좌 좌상
        int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

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

            if (w == 0 || h == 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());
                }
            }
            // input done.


            // BFS
            int answer = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1) {
//                        print(map);
                        answer++;

                        Queue<Pair> que = new ArrayDeque<>();
                        que.add(new Pair(i, j));
                        map[i][j] += answer;

                        while (!que.isEmpty()) {
                            Pair pair = que.poll();

                            for (int k = 0; k < 8; k++) {
                                int x = pair.x + dx[k];
                                int y = pair.y + dy[k];

                                if (0 <= x && x < h && 0 <= y && y < w && map[x][y] == 1) {
                                    que.add(new Pair(x, y));
                                    map[x][y] += answer;
                                }
                            }
                        }
                    }
                }
            }
            System.out.println(answer);
        }
    }

    private static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static void print(int[][] map) {
        System.out.println();
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("================================");
    }
}

🔸 코드 해석 🔸

• 지도 정보를 2차원 배열 map에 입력받는다.
• 지도의 각 칸을 순회하며 1을 찾는다.
  • answer를 +1 한다. 
  • 1부터 BFS로 인접한 칸을 찾아 answer를 더한다.
• answer를 출력한다.

---

🔸 end 🔸

• BFS로 간단히 풀어냈다.
• 태그를 보니 DFS로 풀이할 수 있는데, 생각해보니 최단거리 찾기가 아니므로 BFS보다 DFS가 빠를 것 같다.