[백준 알고리즘] Q17086 아기상어2

 

1. Java 구현

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final String[] firstLine = scanner.nextLine().split(" ");
        final boolean[][] maps = new boolean[Integer.parseInt(firstLine[0])][Integer.parseInt(firstLine[1])];
        final List<Point> points = new ArrayList<>();
        for (int i = 0; i < maps.length; i++) {
            final String[] inputs = scanner.nextLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                maps[i][j] = "1".equals(inputs[j]);
                if(!maps[i][j]) {
                    points.add(new Point(j, i));
                }
            }
        }

        int max = 0;
        for (final Point point : points) {
            max = Math.max(bfs(maps, point), max);
        }

        System.out.println(max);
    }

    private static int bfs(final boolean[][] maps, final Point point) {
        final boolean[][] visited = new boolean[maps.length][maps[0].length];
        final Queue<Point> queue = new LinkedList<>();
        final Queue<Point> temp = new LinkedList<>();
        queue.add(point);

        int len = 0;
        while(!queue.isEmpty()) {
            final Point poll = queue.poll();
            if(!(poll.x < 0 || poll.x >= maps[0].length || poll.y < 0 || poll.y >= maps.length)) {
                if(visited[poll.y][poll.x]) {
                    continue;
                }

                if(maps[poll.y][poll.x]) {
                    return len;
                }

                visited[poll.y][poll.x] = true;

                temp.offer(new Point(poll.x - 1, poll.y - 1));
                temp.offer(new Point(poll.x, poll.y - 1));
                temp.offer(new Point(poll.x + 1, poll.y - 1));
                temp.offer(new Point(poll.x - 1, poll.y));
                temp.offer(new Point(poll.x + 1, poll.y));
                temp.offer(new Point(poll.x - 1, poll.y + 1));
                temp.offer(new Point(poll.x, poll.y + 1));
                temp.offer(new Point(poll.x + 1, poll.y + 1));
            }

            if(queue.isEmpty()) {
                queue.addAll(temp);
                temp.clear();
                len++;
            }
        }

        return 0;
    }

    private static class Point {

        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

}

2. 코드설명

이 문제에서 의미하는 안전거리는 '상어가 없는 빈칸에서 상어가 있는 칸까지의 거리' 이다.

안전거리의 정의만 명확하게 파악하면 BFS 알고리즘을 이용해서 쉽게 풀이가 가능하다. (BFS는 결국은 Queue)

그리고 8가지의 방향으로 모두 이동이 가능하며, 8가지의 방향에 대한 이동을 동일하게 1만큼 이동한다는 것도 명심해야 한다.

 

처음에는 DFS를 이용해서 문제를 풀었다. DFS를 이용하면 대각선을 표현하기가 어려웠다.

그 이유는 (아래 + 옆) 을 이동하고 visited 에 방문표시를 하게 되면 아래 대각선을 할 수 없게 되었다.

그리고 그때 생각났다. 아 해당 포인트를 기점으로 1칸, 2칸, 3칸.. 이렇게 점진적으로 늘려야하는구나.. 그렇다면 BFS!