섬나라 아일랜드(BFS)

BFS(너비 우선 탐색)을 사용하여 섬의 개수를 구한다. 주어진 N*N 크기의 격자판에서 1은 섬, 0은 바다를 나타내며, 상하좌우 및 대각선으로 연결된 1들로 이루어진 영역을 하나의 섬으로 간주한다. 목표는 주어진 격자판에서 몇 개의 섬이 있는지 찾는 것이다.

문제 설명

• 격자판은 N*N 크기로 주어진다.
• 1은 섬을 나타내고, 0은 바다를 나타낸다.
• 상하좌우 및 대각선으로 연결된 1들은 하나의 섬으로 간주된다.
• BFS를 사용해 연결된 섬을 탐색하고, 총섬의 개수를 구한다.

입력 예시

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

 

출력 예시

5

 

해결 과정

1. 격자판 입력받기
먼저 N을 입력받고, N*N 크기의 격자판을 2차원 배열로 저장한다.

 

2. BFS 탐색
BFS는 큐를 이용하여 연결된 모든 섬을 탐색하는 방식이다. 시작 좌표에서부터 큐에 좌표를 추가하고, 큐에서 좌표를 꺼내 상하좌우 및 대각선으로 이동하면서 연결된 모든 섬을 방문 처리한다. 방문한 좌표는 다시 방문하지 않도록 0으로 바꾼다.

 

3. 8방향 탐색
문제에서 상하좌우뿐만 아니라 대각선까지 탐색해야 하므로 총 8방향을 모두 탐색해야 한다. 이를 위해 dx[]와 dy[] 배열을 사용하여 각 방향을 설정한다.

• dx = {-1, 0, 1, 0, -1, 1, 1, -1}
• dy = {0, 1, 0, -1, 1, 1, -1, -1}

4. 큐(Queue) 활용
BFS는 큐를 사용하여 너비 우선 탐색을 수행한다. 섬을 발견하면 큐에 그 좌표를 추가하고, 연결된 모든 1들을 큐에 넣으면서 탐색을 진행한다.

 

5. 섬 개수 세기
이차원 배열을 순회하며 아직 방문하지 않은 섬(1)을 발견할 때마다 섬의 개수를 증가시키고, BFS를 사용해 그 섬에 연결된 모든 부분을 탐색한다.

 

코드

package com.example.codingtest;

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

// 좌표를 저장할 Point 클래스
class Point {
    int x, y;

    // 생성자에서 좌표 (x, y) 설정
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Main {
    // 8방향을 나타내는 dx, dy 배열 (상하좌우 및 대각선)
    static int[] dx = {-1, 0, 1, 0, -1, 1, 1, -1};
    static int[] dy = {0, 1, 0, -1, 1, 1, -1, -1};

    // 격자판과 관련된 변수들
    static int[][] board;  // 섬과 바다의 정보를 담는 2차원 배열
    static int N;  // 격자판의 크기
    static int answer = 0;  // 섬의 개수를 저장하는 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  // 입력을 받기 위한 BufferedReader
        N = Integer.parseInt(br.readLine());  // 격자판 크기 N 입력 받기

        board = new int[N][N];  // N x N 크기의 격자판 배열 초기화

        // N*N 격자판의 정보를 입력 받음
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());  // 한 줄의 입력을 공백으로 구분
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());  // 격자판의 각 좌표에 섬(1) 또는 바다(0) 입력
            }
        }

        // 격자판 전체를 탐색하여 섬을 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 만약 현재 좌표가 섬(1)이라면 BFS를 통해 섬 전체를 탐색
                if (board[i][j] == 1) {
                    answer++;  // 새로운 섬을 발견했으므로 섬 개수 증가
                    board[i][j] = 0;  // 방문한 섬은 0으로 바꿔 다시 방문하지 않도록 처리
                    BFS(i, j, board);  // BFS를 사용하여 연결된 모든 섬을 탐색
                }
            }
        }

        // 섬의 총 개수 출력
        System.out.println(answer);
    }

    // BFS 함수: 큐를 사용하여 섬을 너비 우선으로 탐색
    public static void BFS(int x, int y, int[][] board) {
        Queue<Point> Q = new LinkedList<>();  // 좌표를 저장할 큐 생성
        Q.add(new Point(x, y));  // 시작 좌표를 큐에 추가

        // 큐가 비어 있을 때까지 반복하여 너비 우선 탐색을 수행
        while (!Q.isEmpty()) {
            Point tmp = Q.poll();  // 큐에서 좌표 하나를 꺼냄
            // 8방향으로 탐색
            for (int i = 0; i < 8; i++) {
                int nx = tmp.x + dx[i];  // 새로운 x 좌표
                int ny = tmp.y + dy[i];  // 새로운 y 좌표
                // 새로운 좌표가 격자판 범위 내에 있고, 섬(1)이 있으면
                if (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] == 1) {
                    board[nx][ny] = 0;  // 방문한 섬은 0으로 변경하여 다시 방문하지 않도록 처리
                    Q.add(new Point(nx, ny));  // 새로운 좌표를 큐에 추가하여 탐색 확장
                }
            }
        }
    }
}

• BFS는 큐를 사용해 섬을 탐색하며, 너비 우선으로 연결된 모든 좌표를 차례로 방문한다.
• 상하좌우 및 대각선 8방향을 탐색하여 섬이 연결된지를 확인한다.
• 방문한 섬은 다시 탐색하지 않도록 0으로 처리한다.

 

결론

BFS를 사용한 섬 개수 구하기는 DFS와 유사하지만, 큐를 사용하여 너비 우선으로 탐색을 진행하는 방식이다. 이 방법은 재귀 없이 반복문과 큐를 통해 섬을 탐색하는 데 적합하다.