🔗
풀이
최소 거울의 개수를 찾는 문제라서 최소라는 말만 보고 BFS인가 싶었지만 최단 거리로 도착하는 경우가 반드시 최소 거울의 개수를 보장하지는 않는다. 거울의 개수를 최소로 가진다는 것은 결국 회전하는 횟수가 최소라는 뜻이지 방문해야 할 위치의 수가 최소인 것은 아니기 때문이다.
결국 최소 개수의 거울을 가지는 경우를 우선순위로 하여 탐색을 진행해야 한다. 이때 회전 여부에 따라 거울이 필요한지 아닌지가 결정되기 때문에 이전에 어떤 방향에서 현재 위치로 들어오게 되었는지를 알기 위해 이전 방향의 정보가 필요하다. 종합하면 우선순위 큐에 들어가야 할 좌표가 가져야 할 값들은 다음과 같다.
class Pos implements Comparable<Pos>{
int x, y, d, count;
public Pos(int x, int y, int d, int count) {
this.x = x;
this.y = y;
this.d = d; // 이전 방향의 정보
this.count = count; // 거울의 개수
}
@Override
public int compareTo(Pos o) {
return this.count - o.count;
}
}거울의 개수가 최소인 것을 우선순위로 하도록 최소힙을 사용해 구현하기 위해 compareTo를 오버라이딩했다.
이때 주의해야 할 점은 해당 위치를 재방문하는 것은 가능하지만 이미 같은 방향에서 해당 위치를 방문한 적이 있을 때는 재방문이 불가능하다는 것이다. 결국 이 문제는 이전 방향의 위치에 따라 거울의 개수가 결정되는데 만약 아래 방향으로 이동해서 어떤 위치에 방문할 경우 90도로 회전해서 오른쪽으로 방향을 틀면 거울의 개수가 1개 추가되어야 한다. 하지만 이전에 오른쪽 방향으로 이동해서 같은 위치에 방문했다면 오른쪽으로 이동하는 것은 90도 회전하는 것이 아니기 때문에 거울이 필요하지 않다. 결국 거울의 개수를 결정하는 것은 방향 값이며, 같은 방향으로부터는 다시 방문하지 않아야 하지만 같은 방향이 아닐 경우는 재방문할 수 있도록 해야 하기때문에 별도의 방문처리가 필요하다. 방문처리를 2차원으로 처리할 경우 어떤 방향에서 들어왔는지에 대한 정보가 없어서 같은 방향에서 방문하게 된 경우도 중복으로 처리하게 된다. 그래서 방문처리의 배열을 3차원으로 처리하여 각 좌표 별로 4개 방향에 대한 방문처리를 별도로 해주어야 한다.
해당 메모리 초과 반례반례를 통과한다면 제대로 중복처리를 한 것이다.
import java.util.*;
import java.io.*;
class Pos implements Comparable<Pos>{
int x, y, d, count;
public Pos(int x, int y, int d, int count) {
this.x = x;
this.y = y;
this.d = d;
this.count = count;
}
@Override
public int compareTo(Pos o) {
return this.count - o.count;
}
}
public class Main {
static char[][] MAP;
static int W;
static int H;
static int[][] dir = new int[][] {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
static int[][][] mirror;
static Pos findStart() {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (MAP[i][j] == 'C') {
MAP[i][j] = '.';
return new Pos(i, j, -1, 0);
}
}
}
return null;
}
public static int findC(Pos now) {
PriorityQueue<Pos> pq = new PriorityQueue<>();
pq.add(now);
Pos cur;
while (!pq.isEmpty()) {
cur = pq.poll();
if (MAP[cur.x][cur.y] == 'C') {
return cur.count;
}
for (int i = 0; i < 4; i++) {
// 다음에 이동할 위치 찾기
int nextX = cur.x + dir[i][0];
int nextY = cur.y + dir[i][1];
if (nextX < 0 || nextX >= H || nextY < 0 || nextY >= W || MAP[nextX][nextY] == '*') continue;
if (cur.d != i && cur.d != -1) {
if (mirror[nextX][nextY][i] > cur.count + 1) {
mirror[nextX][nextY][i] = cur.count + 1;
pq.add(new Pos(nextX, nextY, i, cur.count + 1));
}
} else {
if (mirror[nextX][nextY][i] > cur.count) {
mirror[nextX][nextY][i] = cur.count;
pq.add(new Pos(nextX, nextY, i, cur.count));
}
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
MAP = new char[H][W];
for (int i = 0; i < H; i++) {
MAP[i] = br.readLine().toCharArray();
}
mirror = new int[H][W][4];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
Arrays.fill(mirror[i][j], Integer.MAX_VALUE);
}
}
System.out.println(findC(findStart()));
}
}참고
