17086번 - 아기상어2(BFS, 8방향 탐색)

문제:

N x M(둘다 50이하) 크기의 공간에 아기 상어 여러마리가 있다. 상어가 있으면 1, 없으면 0 이다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

 

풀이:

첫번째 칸 부터 안전거리를 찾는 것은 비효율적이라는 생각이 들었다.
N x M 만큼 각 칸의 안전거리를 찾아야 하기 때문이다.
상어의 위치가 주어지기에, 상어의 위치를 기준으로 찾으면 좋겠다고 생각했고,
각 상어의 위치로부터 각 칸의 안전거리를 따로 따로 측정하며, 그 중 가장 작은 안전거리를 저장하면 될 것이라 생각했다.

그러기 위해 머저 아래와 같이 전역변수를 미리 등록한다.

static int N,M;
static int[] xMove = {0,0,-1,1,-1,1,-1,1};
static int[] yMove = {1,-1,0,0,1,-1,-1,1};
static int[][] sd;
static Queue<int[]> shark;
static int max = 0;

• xMove와 yMove는 어떤 지점에서 8방향( →,←,↑,↓,↗,↙,↖,↘)으로 이동할 수 있도록 이동 방향을 저장한다.
  for문을 통해 8번 반복하면, 해당 기능을 수행할 수 있다.
• sd는 안전거리의 약자로, 각 칸의 안전거리를 저장한다. 각 칸의 모든 값은 10000으로 초기화한다.
• shark는 상어의 위치를 저장한다.
• max는 안전거리의 최댓값이다.

위에서 등록한 전역변수를 활용하여 답을 출력하기 위해 아래와 같이 메인 메서드를 작성했다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] nums = br.readLine().split(" ");
    N = Integer.parseInt(nums[0]);
    M = Integer.parseInt(nums[1]);

    sd = new int[N][M];
    shark = new LinkedList<>();

    for (int i = 0; i < N; i++) {
        String[] line = br.readLine().split(" ");
        for (int j = 0; j < M; j++) {
            if (Integer.parseInt(line[j]) == 1) {
                shark.add(new int[]{i, j});
            }
        }
    }

    for (int i = 0; i < N; i++) {
        Arrays.fill(sd[i], 10000);
    }

    while (!shark.isEmpty()) {
        int[] pos = shark.poll();
        int y = pos[0];
        int x = pos[1];
        findShark(y, x);
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            max = Math.max(sd[i][j], max);
        }
    }

    System.out.println(max);
}

sd[][]의 각 칸은 미리 10000으로 초기화 해놓으며,
shark큐에 미리 아기상어의 위치를 저장해 놓는다.

shark 큐에 있는 아기상어의 위치를 기반으로, findShark()메서드를 통해 각 칸의 안전거리를 측정하고,
마지막으로 안전거리 중 최대값을 구해 출력한다.

각 칸의 안전거리를 측정하는 방법은 아래와 같다.

static void findShark(int y, int x) {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{y,x,0});
    sd[y][x] = 0;

    while (!queue.isEmpty()) {
        int[] pos = queue.poll();
        int nowY = pos[0];
        int nowX = pos[1];
        int distance = pos[2];

        for (int i = 0; i < 8; i++) {
            int nextY = nowY + yMove[i];
            int nextX = nowX + xMove[i];

            if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N
                    && sd[nextY][nextX] > distance + 1) {
                queue.add(new int[]{nextY, nextX, distance + 1});
                sd[nextY][nextX] = distance + 1;
            }
        }
    }
}

1. 시작 점을 해당 상어의 위치로 지정하며, 해당 위치의 안전거리는 0이다. 큐에는 상어의 위치와 안전거리를 저장한다.
2. 큐에서 꺼낸 배열에 현 위치(y,x)와 현 안전거리가 포함되어 있다.
3. 8방향 탐색을 실시한다. 각 방향으로 이동할 수 있으면 이동시키고,
   만일 해당 위치에 저장된 안전거리가 지금 측정한 안전거리보다 크다면,
   해당 위치의 안전거리를 지금 측정한 안전거리로 교체한다.
4. 2, 3번 과정을 큐가 빌 동안 반복한다.

위 메서드(bfs)를 통해 불필요한 반복을 최소화하여 각 칸의 최소안전거리를 구할 수 있다.
만일 다음 칸에 이미 최소 안전거리가 저장되어 있다면, 조건문에 의해 큐에 다시 저장되지 않기 때문이다.

 

전체코드:

import java.io.*;
import java.util.*;

public class 아기상어2_17086번 {
    static int N,M;
    static int[] xMove = {0,0,-1,1,-1,1,-1,1};
    static int[] yMove = {1,-1,0,0,1,-1,-1,1};
    static int[][] sd;
    static Queue<int[]> shark;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nums = br.readLine().split(" ");
        N = Integer.parseInt(nums[0]);
        M = Integer.parseInt(nums[1]);

        sd = new int[N][M];
        shark = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                if (Integer.parseInt(line[j]) == 1) {
                    shark.add(new int[]{i, j});
                }
            }
        }

        for (int i = 0; i < N; i++) {
            Arrays.fill(sd[i], 10000);
        }

        while (!shark.isEmpty()) {
            int[] pos = shark.poll();
            int y = pos[0];
            int x = pos[1];
            findShark(y, x);
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                max = Math.max(sd[i][j], max);
            }
        }

        System.out.println(max);
    }

    static void findShark(int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{y,x,0});
        sd[y][x] = 0;

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int nowY = pos[0];
            int nowX = pos[1];
            int distance = pos[2];

            for (int i = 0; i < 8; i++) {
                int nextY = nowY + yMove[i];
                int nextX = nowX + xMove[i];

                if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N
                        && sd[nextY][nextX] > distance + 1) {
                    queue.add(new int[]{nextY, nextX, distance + 1});
                    sd[nextY][nextX] = distance + 1;
                }
            }
        }
    }
}

 

시행착오:

문제에 대한 설명을 작성하며, 쓸모없는 배열을 무려 두개나 발견했다.

사용자의 입력을 모두 저장한 배열 map[][]과 방문한 적이 있는지 검사하는 visited[][]이다.

실제로 해당 배열들을 하나씩 삭제하니 아래처럼 풀이 속도가 더 빨라졌다.

visited 배열은 이미 sd가 그 역할을 대신해주고 있으며, 더욱 효율적이다.

map 배열은 입력받을 때 말고는 전혀 이용되지 않고 있었다.

아기상어들의 위치만 알면 되기에, 전혀 쓸모없는 배열이었다.