BOJ04963 섬의 개수

https://www.acmicpc.net/problem/4963 (opens new window)

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 센다.

WARNING

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

Location

좌표를 관리하기 위한 Location 클래스이다.

private static class Location {
    private int x, y;

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

BFS 활용

모든 섬을 방문하여 방문 처리를 남길 수 있도록 bfs 메서드를 선언하였다. 이전에 상하좌우로 4방향 탐색하는 문제와는 다르게 대각선을 포함하여 총 8개의 방향을 탐색할 수 있다는 점을 유의해야 한다.

private static final int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1};
private static final int[] dy = {0, 1, 0, -1, -1, 1, 1, -1};

private static void bfs(int x, int y) {
    Queue<Location> queue = new LinkedList<>();
    queue.add(new Location(x, y));
    visited[x][y] = true;

    while (!queue.isEmpty()) {
        Location location = queue.poll();
        for (int i = 0; i < 8; i++) {
            x = location.x + dx[i];
            y = location.y + dy[i];
            if (isLocation(x, y)) {
                queue.add(new Location(x, y));
                visited[x][y] = true;
            }
        }
    }
}

private static boolean isLocation(int x, int y) {
    if (x < 0 || x >= h || y < 0 || y >= w || visited[x][y] || graph[x][y] == 0) {
        return false;
    }

    return true;
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ4963 {

    private static int w, h;
    private static int[][] graph;
    private static boolean[][] visited;
    private static final int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1};
    private static final int[] dy = {0, 1, 0, -1, -1, 1, 1, -1};

    private static class Location {
        private int x, y;

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

    private static void bfs(int x, int y) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            for (int i = 0; i < 8; i++) {
                x = location.x + dx[i];
                y = location.y + dy[i];
                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    visited[x][y] = true;
                }
            }
        }
    }

    private static boolean isLocation(int x, int y) {
        if (x < 0 || x >= h || y < 0 || y >= w || visited[x][y] || graph[x][y] == 0) {
            return false;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while ((w = scanner.nextInt()) != 0 && (h = scanner.nextInt()) != 0) {

            graph = new int[h][w];
            visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    graph[i][j] = scanner.nextInt();
                }
            }

            int count = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (graph[i][j] == 1 && !visited[i][j]) {
                        bfs(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }
}

#BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색 #BFS #DFS