백준 : 섬의 개수 (4963)

*** 본 풀이는 java언어를 사용하였습니다 ***

문제 보러가기

 

요약

섬과 바다가 적힌 지도가 주어진다.

섬 주변에 (360 도) 다른 섬이 있으면 하나의 섬이라고 가정한다.

섬의 개수를 출력하라.

문제를 보자마자 그래프 탐색으로 풀어야 겠다는 생각이 들었다면

문제를 쉽게 풀 수 있었을 것이다.

그래프 탐색은 BFS와 DFS가 있는데, 필자는 BFS로 풀었다.

 

참고 )

보통 DFS는 스택이나 재귀함수를 통해서 구현하고,

BFS는 큐를 이용해서 구현한다.

 

풀이

여러가지 방법이 있겠지만, 필자의 경우 탐색하는 위치가 섬 일 경우 BFS 탐색을 시작하게끔 구현했다.

public static int solution(int[][] map) {
    int result = 0;
    boolean[][] visited = new boolean[map.length][map[0].length];
    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map[0].length; j++) {
            result = bfs(i, j, map, visited, result);
        }
    }
    return result;
}

 

이중 for문을 통해서 모든 위치를 확인하고, 해당 위치가 섬이라면 BFS 탐색을 시작한다.

섬이 아니라면 다음과 같이 메서드를 빠져 나오게 구현했다.

private static int bfs(int x, int y, int[][] map, boolean[][] visited, int result) {
	if (visited[x][y] || map[x][y] == 0) return result;
...

 

해당 위치가 섬이라면, 위치 값을 큐에 넣어준다.

Queue<Integer> queue = new LinkedList<>();
queue.add(x);
queue.add(y);
visited[x][y] = true;

 

visited 배열을 만든 이유

이중 for문을 돌면서 모든 배열을 탐색 할텐데

1번 탐색한 곳은 다시는 탐색할 필요가 없으므로 방문 했다는 표시를 하기 위해서다.

 

while (!queue.isEmpty()) {
    int currentX = queue.poll();
    int currentY = queue.poll();

    for (int i = 0; i < X_DIR.length; i++) {
        int nextX = currentX + X_DIR[i];
        int nextY = currentY + Y_DIR[i];

        // 범위 체크
        if (nextX < 0 || nextY < 0 || nextX > map.length - 1 || nextY > map[0].length - 1) continue;

        // 방문 체크 및 바다인가
        if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;

        queue.add(nextX);
        queue.add(nextY);
        visited[nextX][nextY] = true;
    }
}

이 부분이 BFS의 핵심인 부분인데

아까 위에서 설명했던 요구사항을 다시한번 살펴보자.

섬 주변에 (360 도) 다른 섬이 있으면 하나의 섬이라고 가정한다.

섬과 근접한 다른 섬이 있다면 하나의 섬으로 간주하므로,
인접한 섬이 있는지 360도로 하나씩 돌면서 파악하는 것이다.

 

어떻게 360도의 위치를 파악하죠?

private static int[] X_DIR = {0, 1, 1, 1, 0, -1, -1, -1}; // 상 부터 오른쪽으로 360도 체크
private static int[] Y_DIR = {-1, -1, 0, 1, 1, 1, 0, -1};

이처럼 다음 탐색할 곳을 배열로 나눠놓으면 된다.

 

만약 현재 위치가 1,1 이다.

근접한 섬이 있는지 파악해야 하므로 위쪽 부터 시계방향으로 탐색하도록 구현했다.

 

먼저, 맨 위의 탐색을 해보자.

X_DIR의 0 번째 인덱스 값은 0, Y_DIR의 0 번째 인덱스 값은 -1 이므로,

현재 위치의 x 값에 X_DIR의 값을 더하고, 현재 위치의 y 값에 Y_DIR의 값을 더하면 다음과 같다.

 

다음 탐색 할 x 값 : 1 + 0 = 1

다음 탐색 할 y 값 : 1 - 1 = 0

 

즉 1, 0 위치가 다음 탐색 할 위치다.

이것을 코드로 표현한 부분은 다음과 같다.

for (int i = 0; i < X_DIR.length; i++) {
    int nextX = currentX + X_DIR[i];
    int nextY = currentY + Y_DIR[i];
    ...
}

 

범위가 정상적인 범위인지, 해당 섬을 처음 방문하는 것인지, 섬이 맞는지를 확인하는 조건을 모두 통과하게 되면

탐색해야 할 섬이라는 것이 보장되므로 큐에 넣어준다.

 

큐가 모두 비어지고 반복문을 마치면 섬 하나의 탐색이 종료됬다는 것을 의미하므로,

섬의 개수를 1개 증가시킨다.

while (!queue.isEmpty()) {
   ... 
}
return ++result;

 

제출 코드

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            int[] mapSize = Arrays.stream(br.readLine().split(" "))
                                  .mapToInt(Integer::parseInt)
                                  .toArray();

            if (mapSize[0] == 0 && mapSize[1] == 0) break;

            int[][] map = new int[mapSize[1]][mapSize[0]];
            for (int i = 0; i < map.length; i++) {
                map[i] = Arrays.stream(br.readLine().split(" "))
                               .mapToInt(Integer::parseInt)
                               .toArray();
            }
            bw.write(String.valueOf(Solution.solution(map)));
            bw.newLine();
        }
        bw.flush();
    }
}

class Solution {
    private static int[] X_DIR = {0, 1, 1, 1, 0, -1, -1, -1}; // 상 부터 오른쪽으로 360도 체크
    private static int[] Y_DIR = {-1, -1, 0, 1, 1, 1, 0, -1};

    public static int solution(int[][] map) {
        int result = 0;
        boolean[][] visited = new boolean[map.length][map[0].length];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                result = bfs(i, j, map, visited, result);
            }
        }
        return result;
    }

    private static int bfs(int x, int y, int[][] map, boolean[][] visited, int result) {
        if (visited[x][y] || map[x][y] == 0) return result;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        queue.add(y);
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int currentX = queue.poll();
            int currentY = queue.poll();

            for (int i = 0; i < X_DIR.length; i++) {
                int nextX = currentX + X_DIR[i];
                int nextY = currentY + Y_DIR[i];

                // 범위 체크
                if (nextX < 0 || nextY < 0 || nextX > map.length - 1 || nextY > map[0].length - 1) continue;

                // 방문 체크 및 바다인가
                if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;

                queue.add(nextX);
                queue.add(nextY);
                visited[nextX][nextY] = true;
            }
        }
        return ++result;
    }
}

 

회고

맨 처음에는 위치 값을 가지는 Position 객체를 만들어서 사용했는데 메모리 초과로 실패했다..

private static class Position {
    ...
}

내부 클래스 방식으로 사용했었는데, static이라서 객체를 사용하지 않음에도

GC에 의해 삭제되지 않아서 객체가 메모리에 계속 쌓이다 보니 메모리가 터진듯하다.

객체 사용을 하지 않고 Queue에 x 값과 y 값을 직접 add 하는 것으로 로직을 수정하니 통과했다.

다음 부터는 좀 더 신중히 생각하고 코딩해야 할듯..

 

오랜만에 그래프 알고리즘을 접하니까 공식을 다 까먹어서 시간이 좀 오래걸렸다..

그래도 기억을 살려 혼자 힘으로 스스로 풀었다는 것에는 만족..

BFS와 DFS문제를 더 많이 풀어야 겠다.