문제
N x M 교실에서 시작점 S에서 출발하여 두 개의 배달 지점 C를 모두 방문하는 최소 시간을 구하라. 같은 방향으로 연속 이동할 수 없다.
입력
첫째 줄에 N, M, 이후 N줄에 교실 맵이 주어진다 (S: 시작, C: 배달 지점, #: 벽, .: 빈 공간).
출력
최소 이동 시간을 출력한다. 불가능하면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 3 S.C ... | -1 |
풀이
4차원 방문 배열을 사용하는 BFS로 (방향, 행, 열, 배달 상태)를 추적한다.
- 시작점과 두 배달 지점의 좌표를 파싱한다
- BFS 상태를 (이전 방향, x, y, 시간, 배달 완료 비트마스크)로 정의한다
- 이전과 같은 방향으로는 이동할 수 없으므로 4방향 중 이전 방향을 제외한다
- 배달 지점 도착 시 check 비트를 갱신하며, check가 3(두 곳 모두 방문)이 되면 시간을 반환한다
visited[방향][x][y][check]로 중복 상태를 제거한다
핵심 아이디어: 같은 방향 연속 이동 금지 제약이 있으므로 이전 방향을 상태에 포함해야 하며, 배달 완료 여부를 비트마스크로 관리한다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day780BOJ1175배달 {
static int N, M;
static char[][] classRoom;
static int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };
static class Node {
int dir, x, y, time, check;
public Node(int dir, int x, int y, int time, int check) {
this.dir = dir;
this.x = x;
this.y = y;
this.time = time;
this.check = check;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
classRoom = new char[N][];
Node start = null;
Node[] end = new Node[2];
for (int i = 0, idx = 0; i < N; i++) {
classRoom[i] = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
char now = classRoom[i][j];
if (now == 'S')
start = new Node(-1, i, j, 0, 0);
else if (now == 'C')
end[idx++] = new Node(-1, i, j, 0, 0);
}
}
System.out.println(bfs(start, end));
}
private static int bfs(Node start, Node[] end) {
boolean[][][][] visited = new boolean[4][N][M][3];
for (int i = 0; i < 4; i++)
visited[i][start.x][start.y][0] = true;
Queue<Node> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()) {
Node now = q.poll();
if (now.x == end[0].x && now.y == end[0].y && now.check != 1)
now.check += 1;
else if (now.x == end[1].x && now.y == end[1].y && now.check != 2)
now.check += 2;
if (now.check == 3)
return now.time;
for (int i = 0; i < 4; i++) {
if (now.dir == i)
continue;
int nextX = now.x + dx[i];
int nextY = now.y + dy[i];
if (!isInRange(nextX, nextY) || classRoom[nextX][nextY] == '#' || visited[i][nextX][nextY][now.check])
continue;
visited[i][nextX][nextY][now.check] = true;
q.offer(new Node(i, nextX, nextY, now.time + 1, now.check));
}
}
return -1;
}
private static boolean isInRange(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
}복잡도
- 시간: O(N * M * 4 * 3)
- 공간: O(N * M * 4 * 3)