[백준] 2151. 거울 설치

문제 링크

[백준] 2151. 거울 설치

풀이 과정

거울을 통해 방향을 수직으로 변경할 수 있으므로, 상하좌우 네 방향에 대한 거울 사용 횟수 저장하기 위해, 3차원 visit 배열을 이용했습니다. 각 배열 요소의 인덱스는 무슨 방향으로 해당 좌표에 접근했는 지를 의미하며, 그 값은 거울의 최소 사용 횟수를 의미합니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        Arrays.fill(visit[i][j], Integer.MAX_VALUE);
    }
}

먼저 모든 배열 요소들을 INF 값으로 초기화 합니다. 이는, 더 작은 횟수의 거울 사용으로 인접한 좌표를 방문할 수 있는 지를 확인하기 위함입니다.

Queue<Point> queue = new LinkedList<>();

for (int d = 0; d < 4; d++) {
    visit[start.x][start.y][d] = 0;
    queue.add(new Point(start.x, start.y, d));
}

다음으로 큐를 생성한 뒤 시작점에 대한 상하좌우 방향의 거울 사용 횟수를 0으로 초기화 한 후, 큐에 넣어줍니다.

while (!queue.isEmpty()) {
    Point now = queue.poll();

    int nx = now.x + dx[now.dir];
    int ny = now.y + dy[now.dir];

    if (!inRange(nx, ny) || map[nx][ny] == '*') continue;

    if (map[nx][ny] == '.') {
        if (visit[nx][ny][now.dir] > visit[now.x][now.y][now.dir]) {
            visit[nx][ny][now.dir] = visit[now.x][now.y][now.dir];
            queue.add(new Point(nx, ny, now.dir));
        }
    } else if (map[nx][ny] == '#') {
        if (visit[nx][ny][now.dir] > visit[now.x][now.y][now.dir])
            visit[nx][ny][now.dir] = visit[now.x][now.y][now.dir];
    } else if (map[nx][ny] == '!') {
        if (visit[nx][ny][now.dir] > visit[now.x][now.y][now.dir]) {
            visit[nx][ny][now.dir] = visit[now.x][now.y][now.dir];
            queue.add(new Point(nx, ny, now.dir));
        }

        int[] next_dir = changeDir(now.dir);

        if (visit[nx][ny][next_dir[0]] > visit[now.x][now.y][now.dir] + 1) {
            visit[nx][ny][next_dir[0]] = visit[now.x][now.y][now.dir] + 1;
            queue.add(new Point(nx, ny, next_dir[0]));
        }

        if (visit[nx][ny][next_dir[1]] > visit[now.x][now.y][now.dir] + 1) {
            visit[nx][ny][next_dir[1]] = visit[now.x][now.y][now.dir] + 1;
            queue.add(new Point(nx, ny, next_dir[1]));
        }
    }
}

이제 큐에 담긴 네 요소(시작 좌표에 대한 상하좌우 방향 정보)를 시작으로 BFS 탐색을 진행합니다. 규칙은 다음과 같습니다.

• 거울을 놓지 않을 때(다음 요소가 . 이거나 # 일 때)엔 이동 방향을 유지한 채 다음 좌표로 이동을 합니다.
• 거울을 놓을 수 있는 자리에선 다음과 같이 동작합니다.
  1. 먼저 거울을 두지 않은 채로 이동해봅니다.
  2. 거울을 둔 채 이동합니다. 거울을 통해 두 가지 방향으로 진행 방향이 바뀔 수 있습니다. 따라서, 두 방향 모두 진행해봅니다.
• 다음 좌표에서의 거울 사용 횟수와 현재 좌표까지 진행했을 때의 거울 사용 횟수를 비교해봅니다.
  1. 현재 좌표에 거울을 놓지 않는다면, 단순히 현재와 다음 좌표에서의 거울 사용 횟수를 비교한뒤, 다음 좌표에서의 거울 사용 횟수가 더 큰 값을 가진다면 현재 것으로 갱신해줍니다.
  2. 현재 좌표에 거울을 둔다면, 현재까지의 거울 사용 횟수에다가 거울을 두는 횟수 1을 더한 값과 비교합니다.

코드

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

public class Main {
    static int N;
    static char[][] map;
    static int[][][] visit;
    static Point start, end;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new char[N][N];
        visit = new int[N][N][4];
        boolean first = true;

        for (int i = 0; i < N; i++) {
            String s = sc.next();
            for (int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j);

                if (map[i][j] == '#') {
                    if (first) {
                        start = new Point(i, j);
                        first = false;
                    } else end = new Point(i, j);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Arrays.fill(visit[i][j], Integer.MAX_VALUE);
            }
        }

        Queue<Point> queue = new LinkedList<>();

        for (int d = 0; d < 4; d++) {
            visit[start.x][start.y][d] = 0;
            queue.add(new Point(start.x, start.y, d));
        }

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            int nx = now.x + dx[now.dir];
            int ny = now.y + dy[now.dir];

            if (!inRange(nx, ny) || map[nx][ny] == '*') continue;

            if (map[nx][ny] == '.') {
                if (visit[nx][ny][now.dir] > visit[now.x][now.y][now.dir]) {
                    visit[nx][ny][now.dir] = visit[now.x][now.y][now.dir];
                    queue.add(new Point(nx, ny, now.dir));
                }
            } else if (map[nx][ny] == '#') {
                if (visit[nx][ny][now.dir] > visit[now.x][now.y][now.dir])
                    visit[nx][ny][now.dir] = visit[now.x][now.y][now.dir];
            } else if (map[nx][ny] == '!') {
                if (visit[nx][ny][now.dir] > visit[now.x][now.y][now.dir]) {
                    visit[nx][ny][now.dir] = visit[now.x][now.y][now.dir];
                    queue.add(new Point(nx, ny, now.dir));
                }

                int[] next_dir = changeDir(now.dir);

                if (visit[nx][ny][next_dir[0]] > visit[now.x][now.y][now.dir] + 1) {
                    visit[nx][ny][next_dir[0]] = visit[now.x][now.y][now.dir] + 1;
                    queue.add(new Point(nx, ny, next_dir[0]));
                }

                if (visit[nx][ny][next_dir[1]] > visit[now.x][now.y][now.dir] + 1) {
                    visit[nx][ny][next_dir[1]] = visit[now.x][now.y][now.dir] + 1;
                    queue.add(new Point(nx, ny, next_dir[1]));
                }
            }
        }

        for (int d = 0; d < 4; d++) {
            answer = Math.min(answer, visit[end.x][end.y][d]);
        }

        System.out.println(answer);
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > N - 1) return false;
        return true;
    }

    static int[] changeDir(int dir) {
        if (dir == 0 || dir == 1) return new int[]{2, 3};
        else return new int[]{0, 1};
    }

    static class Point {
        int x, y, dir;

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

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