[4963] 섬의 개수

🔗 문제 링크

https://www.acmicpc.net/problem/4963

🔍 문제 설명

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

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

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

⚠️ 제한사항

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

• 입력의 마지막 줄에는 0이 두 개 주어진다.

---

🗝 풀이 (언어 : Java)

재귀호출 DFS로 풀었다.

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

public class Main {

    private static final int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; //상, 하, 좌, 우
    private static final int[][] dir2 = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; //상좌, 상우, 하좌, 하우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer wh = new StringTokenizer(br.readLine(), " ");
            int column = Integer.parseInt(wh.nextToken());
            int row = Integer.parseInt(wh.nextToken());
            if (row == 0 && column == 0) {
                br.close();
                break;
            }
            int[][] map = new int[row][column];
            for (int i = 0; i < row; i++) {
                StringTokenizer landSeaSt = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < column; j++) {
                    int landSea = Integer.parseInt(landSeaSt.nextToken());
                    map[i][j] = landSea;
                }
            }
            System.out.println(countIsland(row, column, map));
        }
    }

    public static int countIsland(int row, int column, int[][] map) {
        boolean[][] visited = new boolean[row][column];
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    dfs(new int[] {i, j}, map, visited);
                    count++;
                }
            }
        }
        return count;
    }

    public static void dfs(int[] position, int[][] map, boolean[][] visited) {
        visited[position[0]][position[1]] = true;
        for (int i = 0; i < 4; i++) {
            checkVisited(position, map, visited, dir, i);
            checkVisited(position, map, visited, dir2, i);
        }
    }

    private static void checkVisited(int[] position, int[][] map, boolean[][] visited, int[][] dirMatrix, int dirIdx) {
        if (position[0] + dirMatrix[dirIdx][0] >= 0
            && position[0] + dirMatrix[dirIdx][0] < map.length
            && position[1] + dirMatrix[dirIdx][1] >= 0
            && position[1] + dirMatrix[dirIdx][1] < map[0].length
            && map[position[0] + dirMatrix[dirIdx][0]][position[1] + dirMatrix[dirIdx][1]] == 1
            && !visited[position[0] + dirMatrix[dirIdx][0]][position[1] + dirMatrix[dirIdx][1]]) {
            dfs(new int[] {position[0] + dirMatrix[dirIdx][0], position[1] + dirMatrix[dirIdx][1]}, map, visited);
        }
    }

}