[BOJ/Java] 섬의 개수 (4963)

섬의 개수 (4963)

1. 문제 분석

문제 개요:

• 2차원 배열로 주어진 지도에서 섬의 개수를 세는 문제이다. 지도의 각 칸은 바다(0) 또는 땅(1)으로 표시된다. 인접한 땅(상하좌우, 대각선 방향)이 연결되어 하나의 섬을 형성하며, 지도에 존재하는 섬의 총 개수를 구해야 한다.

입력 형식

• 첫 줄에는 지도의 너비 w와 높이 h가 주어진다.
• 다음 h개의 줄에 걸쳐서 지도의 정보가 주어진다. 지도의 정보는 0과 1로 이루어진 숫자가 공백으로 구분된다.
• 입력의 마지막 줄에서 w와 h가 둘 다 0이면 입력이 종료된다.

출력 형식

• 각 테스트 케이스에 대해 섬의 개수를 출력한다.

2. 알고리즘 종류

• 이 문제는 DFS(깊이 우선 탐색) 알고리즘을 사용하는 문제이다. 해당 문제는 2차원 배열을 순회하면서 연결된 모든 섬의 부분을 탐색하여 섬의 개수를 세는 방식으로 해결한다.

3. 주요 부분 및 코드 작성 방법

1. DFS 사용

• DFS를 사용하여 각 위치에서 연결된 섬의 모든 부분을 탐색하고, 탐색이 완료된 섬의 개수를 증가시킨다.

2. 지도 탐색 및 섬의 개수 세기

• 전체 지도를 순회하면서, 아직 방문하지 않은 땅(1)을 발견하면 DFS를 통해 해당 섬의 모든 부분을 방문 처리하고 섬의 개수를 증가시킨다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
    StringBuilder sb = new StringBuilder(); // 결과 출력을 위한 StringBuilder 객체 생성
  
    while (true) {
        StringTokenizer st = new StringTokenizer(br.readLine()); // 입력된 줄을 공백을 기준으로 나누어 처리
        w = Integer.parseInt(st.nextToken()); // 너비 입력
        h = Integer.parseInt(st.nextToken()); // 높이 입력
        answer = 0; // 섬의 개수를 저장할 변수 초기화
  
        if(w == 0 && h == 0) break; // 너비와 높이가 둘 다 0이면 입력 종료
        map = new int[h][w]; // 지도의 크기만큼 2차원 배열 초기화
        visited = new boolean[h][w]; // 방문 여부를 체크할 2차원 배열 초기화

  • BufferedReader를 사용해 입력을 처리한다. w와 h가 0이면 입력을 종료한다.

• 지도 초기화 및 입력된 위치 저장

    for(int i = 0; i < h; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 한 줄의 입력을 공백을 기준으로 나누어 처리
        for(int j = 0; j < w; j++) {
            map[i][j] = Integer.parseInt(st.nextToken()); // 지도 정보를 2차원 배열에 저장
        }
    }

  • 입력받은 지도 정보를 2차원 배열 map에 저장한다.

• DFS를 통한 섬의 탐색

    for(int i = 0; i < h; i++) { // 지도의 모든 행 순회
        for(int j = 0; j < w; j++) { // 지도의 모든 열 순회
            if (!visited[i][j] && map[i][j] == 1) { // 방문하지 않았고, 현재 위치가 땅(1)인 경우
                dfs(i, j); // DFS를 통해 섬의 모든 부분 탐색
                answer++; // 탐색 완료 후 섬의 개수 증가
            }
        }
    }
    sb.append(answer).append("\n"); // 결과를 StringBuilder에 저장

  • 지도의 모든 칸을 순회하며, 방문하지 않은 땅을 발견하면 DFS를 호출해 해당 섬의 모든 부분을 탐색하고, 섬의 개수를 증가시킨다.

• 결과 출력

    System.out.println(sb); // 최종 결과 출력

  • 모든 테스트 케이스에 대해 섬의 개수를 출력한다.

(2) DFS 함수 (dfs)

• 초기화

    visited[r][c] = true; // 현재 위치를 방문 처리

  • DFS 탐색을 시작한 위치를 방문 처리한다.

• 탐색

    for (int i = 0; i < 8; i++) { // 8방향으로 탐색 (상하좌우 및 대각선)
        int nr = r + dr[i]; // 새로운 행 위치
        int nc = c + dc[i]; // 새로운 열 위치
        if (nr < 0 || nc < 0 || nr >= h || nc >= w || visited[nr][nc]) continue; // 지도를 벗어나거나 이미 방문한 경우 건너뜀
        if (map[nr][nc] == 1) dfs(nr, nc); // 인접한 땅을 발견하면 DFS를 통해 탐색 계속
    }

  • 현재 위치에서 8방향으로 인접한 칸들을 탐색하며, 범위 내에 있고 방문하지 않았으며 땅인 경우 DFS를 재귀 호출하여 계속 탐색을 이어간다.

5. 전체 코드

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

public class BOJ4963 {
    static int w, h, answer;
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1}; // 방향 배열: 상하좌우 및 대각선 방향
    static int[] dc = {0, 0, -1, 1, -1, 1, -1, 1}; // 방향 배열: 상하좌우 및 대각선 방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringBuilder sb = new StringBuilder(); // 결과 출력을 위한 StringBuilder 객체 생성

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine()); // 입력된 줄을 공백을 기준으로 나누어 처리
            w = Integer.parseInt(st.nextToken()); // 너비 입력
            h = Integer.parseInt(st.nextToken()); // 높이 입력
            answer = 0; // 섬의 개수를 저장할 변수 초기화

            if(w == 0 && h == 0) break; // 너비와 높이가 둘 다 0이면 입력 종료
            map = new int[h][w]; // 지도의 크기만큼 2차원 배열 초기화
            visited = new boolean[h][w]; // 방문 여부를 체크할 2차원 배열 초기화

            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()); // 지도 정보를 2차원 배열에 저장
                }
            }

            for(int i = 0; i < h; i++) { // 지도의 모든 행 순회
                for(int j = 0; j < w; j++) { // 지도의 모든 열 순회
                    if (!visited[i][j] && map[i][j] == 1) { // 방문하지 않았고, 현재 위치가 땅(1)인 경우
                        dfs(i, j); // DFS를 통해 섬의 모든 부분 탐색
                        answer++; // 탐색 완료 후 섬의 개수 증가
                    }
                }
            }
            sb.append(answer).append("\n"); // 결과를 StringBuilder에 저장
        }
        System.out.println(sb); // 최종 결과 출력
    }

    public static void dfs(int r, int c) {
        visited[r][c] = true; // 현재 위치를 방문 처리
        for (int i = 0; i < 8; i++) { // 8방향으로 탐색 (상하좌우 및 대각선)
            int nr = r + dr[i]; // 새로운 행 위치
            int nc = c + dc[i]; // 새로운 열 위치
            if (nr < 0 || nc

 < 0 || nr >= h || nc >= w || visited[nr][nc]) continue; // 지도를 벗어나거나 이미 방문한 경우 건너뜀
            if (map[nr][nc] == 1) dfs(nr, nc); // 인접한 땅을 발견하면 DFS를 통해 탐색 계속
        }
    }
}