[백준] 4963. 섬의 개수

문제 출처

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

문제 설명

바다와 땅이 있다.

인접한 땅들은 한 개의 섬이다.

섬의 개수를 세어라.

문제 풀이

완전 탐색으로 땅을 찾는다.

땅을 찾으면 인접한 모든 땅을 너비 우선 탐색으로 방문 표시한다.

땅을 찾은 횟수가 섬의 개수가 된다.

코드

 

코드 해설

    public static void main(String[] args) throws IOException {
        readInput();
        while (!(R == 0 && C == 0)) {
            int answer = getIslandCount();
            System.out.println(answer);
            readInput();
        }
    }

항상 메인문은 심플하게.

1. 입력을 받는다.

2. 계산한다.

3. 출력한다.

반복.

 

    public static int getIslandCount() {
        int islandCount = 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (map[r][c] == 1) {
                    islandCount++;
                    bfs(r, c);
                }
            }
        }
        return islandCount;
    }

getIslandCount() 는 완전 탐색으로 땅을 찾는다.

땅을 찾았다면 새로운 섬을 하나 찾은 것이다.

모든 인접한 땅을 방문 표시하는 건 bfs() 가 한다.

 

    public static void bfs(int r, int c) {
        final int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
        final int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
        Queue<int[]> queue = new LinkedList();
        queue.offer(new int[] {r, c});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int d = 0; d < dr.length; d++) {
                int[] next = new int[] {cur[0] + dr[d], cur[1] + dc[d]};
                if (inRange(next[0], next[1]) && map[next[0]][next[1]] == 1) {
                    queue.offer(next);
                    map[next[0]][next[1]] = 2;
                }
            }
        }
    }

bfs()는 인접한 모든 땅에 방문 표시를 한다.

인접한 땅이란 8방향에 있는 땅을 말한다.

8방향으로 갈 수 있는 모든 땅을 큐에 넣으면서 방문한다.

큐가 비었다면 더이상 인접한 땅이 없는 것이다.