백준 - 4963 - 섬의 개수

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

4963번: 섬의 개수

package bfs;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

/**
 * 백준 - 4963
 */
public class 섬의개수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String[] inputs = sc.nextLine().split(" ");
            int width = Integer.parseInt(inputs[0]);
            int height = Integer.parseInt(inputs[1]);

            if (width == 0 && height == 0) {
                break;
            }

            int[][] map = new int[height][width];
            for (int i = 0; i < height; i++) {
                map[i] = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            }

            int number = countLand(map);
            System.out.println(number);
        }
    }

    private static int countLand(int[][] map) {
        int count = 0;

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 0 || map[i][j] == 2) {
                    continue;
                }
                bfs(map, new int[]{i, j});
                count++;
            }
        }
        return count;
    }

    private static void bfs(int[][] map, int[] startPos) {
        Queue<int[]> queue = new ArrayDeque<>();
        int[][] directions = new int[][]{{-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}};
        queue.offer(startPos);
        map[startPos[0]][startPos[1]] = 2; // 방문 표시

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            for (int n = 0; n < directions.length; n++) { // 주변을 살핌
                int nextI = currentPos[0] + directions[n][0];
                int nextJ = currentPos[1] + directions[n][1];
                if (nextI < 0 || nextJ < 0 || nextI > map.length - 1 || nextJ > map[0].length - 1
                        || map[nextI][nextJ] == 0 || map[nextI][nextJ] == 2) {
                    continue; // 방문할 수 없는 곳
                }
                queue.offer(new int[]{nextI, nextJ});
                map[nextI][nextJ] = 2;
            }
        }
    }
}

오랜만에 다시 알고리즘 공부를 시작했습니다.

다시 하려니까 예전에 했던 능숙함은 다 사라졌네요 ㅜ

BFS를 해봤는데 처음에 메모리 초과 이슈가 났습니다.

이유는 BFS는 큐에 넣을 때 방문 체크를 해야합니다.

오랜만에 하다보니 제가 큐에서 뺄때 방문 체크를 하여 중복 검사가 일어났습니다^^;