[BOJ/Java] 4963. 섬의 개수

[BOJ/Java] 4963. 섬의 개수

---

문제 해석

이 문제는 2차원 맵에서 연결된 땅의 덩어리(섬)의 개수를 찾는 문제이다. 맵은 0(바다)과 1(땅)로 구성되어 있으며, 8방향(수직, 수평, 대각선)으로 연결된 땅은 하나의 섬으로 간주된다. 입력의 끝은 너비와 높이가 모두 0인 경우로 주어진다.

풀이 과정

• io 함수는 여러 테스트 케이스를 처리하며 각 케이스에 대한 맵 정보를 입력받고, 각 위치에서 섬의 개수를 계산한다.
• sol 함수는 주어진 위치에서 BFS를 사용하여 섬을 탐색하고, 방문한 위치는 visited 배열을 통해 체크한다. 연결된 모든 땅을 방문하면 섬 하나의 탐색이 완료된다.
• checkStatus 함수는 주어진 위치가 맵 내부에 있고, 방문하지 않은 땅인지 확인한다.

코드

package edu.ssafy.im.BOJ.Silver.S2.No4963;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    int[][] graph; // 맵 데이터 저장
    boolean[][] visited; // 방문 여부 저장
    int[][] direction = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; // 8방향 이동 벡터

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        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; // 종료 조건

            graph = 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++) {
                    graph[i][j] = Integer.parseInt(st.nextToken()); // 맵 정보 입력
                }
            }

            int ans = 0; // 섬의 개수
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!visited[i][j] && graph[i][j] == 1)
                        ans += sol(i, j); // 섬의 개수 계산
                }
            }

            sb.append(ans).append("\n"); // 결과 문자열 추가
        }
        bw.write(sb.toString()); // 출력
        bw.flush();
        bw.close();
    }

    private int sol(int x, int y) {
        Queue<Point> queue = new ArrayDeque<>(); // BFS를 위한 큐
        queue.offer(new Point(x, y)); // 시작 위치 큐에 추가
        visited[x][y] = true; // 방문 처리

        while(!queue.isEmpty()) {
            Point p = queue.poll(); // 큐에서 위치 꺼내기
            for (int d = 0; d < direction.length; d++) { // 모든 방향에 대해
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (checkStatus(nx, ny)) { // 이동 가능한 위치면
                    visited[nx][ny] = true; // 방문 처리
                    queue.offer(new Point(nx, ny)); // 큐에 추가
                }
            }
        }

        return 1; // 연결된 섬을 하나 탐색 완료
    }

    private boolean checkStatus(int x, int y) {
        return 0 <= x && x < graph.length && 0 <= y && y < graph[0].length && !visited[x][y] && graph[x][y] == 1; // 이동 가능 조건
    }

    class Point {
        int x, y; // 위치 정보

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

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(W×H)로, W는 너비, H는 높이이며, 각 위치를 한 번씩만 방문한다.

느낀점

이 문제를 통해 2차원 격자에서 BFS를 사용하여 지정된 조건에 따라 연결된 구성 요소를 찾는 방법을 배웠다. 다양한 방향의 이동을 처리하고, 조건에 따라 효과적으로 탐색을 수행하는 것이 중요하다는 것을 깨달았다. 이러한 문제 해결 방법은 다른 유사한 문제에도 적용할 수 있다.