https://www.acmicpc.net/problem/1726
처음에 최단경로를 구할 때 코드트리 메두사 문제처럼 최단경로를 미리 저장해 놓고 따라가는 방식으로 구현하려고 했다. 그래서 해당 코드를 바로 구현했는데 구현하자마자 반례가 생각났다.
이 문제는 방향까지 고려해야 하기 때문에 단순히 최단거리라고 해서 최단시간이 되지는 않는다. 또한, 한 번에 3칸씩 갈 수 있기 때문에 단순히 한 칸 한 칸씩 최단거리를 구하는 건 무의미하다. 그래서 방향까지 고려해서 bfs를 돌려주었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main {
static int M, N;
static int[][] board;
static int si, sj, sd, ei, ej, ed;
static int[] di = { 0, 0, 1, -1 };
static int[] dj = { 1, -1, 0, 0 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
board = new int[M][N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
si = Integer.parseInt(st.nextToken()) - 1;
sj = Integer.parseInt(st.nextToken()) - 1;
sd = Integer.parseInt(st.nextToken()) - 1;
st = new StringTokenizer(br.readLine());
ei = Integer.parseInt(st.nextToken()) - 1;
ej = Integer.parseInt(st.nextToken()) - 1;
ed = Integer.parseInt(st.nextToken()) - 1;
ArrayDeque<int[]> dq = new ArrayDeque<>();
boolean[][][] visited = new boolean[M][N][4];
dq.add(new int[] { si, sj, sd, 0 });
visited[si][sj][sd] = true;
while (!dq.isEmpty()) {
int[] current = dq.poll();
int ci = current[0];
int cj = current[1];
int cd = current[2];
int time = current[3];
if (ci == ei && cj == ej && cd == ed) {
System.out.println(time);
break;
}
for (int s = 1; s <= 3; s++) {
int ni = ci + di[cd] * s;
int nj = cj + dj[cd] * s;
if (!validate(ni, nj) || board[ni][nj] == 1) break;
if (visited[ni][nj][cd]) continue;
visited[ni][nj][cd] = true;
dq.add(new int[] { ni, nj, cd, time + 1 });
}
for (int nd = 0; nd < 4; nd++) {
if (cd == nd || visited[ci][cj][nd]) continue;
if ((cd == 1 && nd == 0) || (cd == 0 && nd == 1) || (cd == 2 && nd == 3)
|| (cd == 3 && nd == 2)) {
dq.add(new int[] { ci, cj, nd, time + 2 });
} else {
dq.add(new int[] { ci, cj, nd, time + 1 });
}
visited[ci][cj][nd] = true;
}
}
}
private static boolean validate(int ni, int nj) {
return 0 <= ni && ni < M && 0 <= nj && nj < N;
}
}
'PS > 백준' 카테고리의 다른 글
[백준] 11779번 최소비용 구하기 2 (Java) (0) | 2025.07.08 |
---|---|
[백준] 13549번 숨바꼭질3 (Java) (0) | 2025.07.06 |
[백준] 1461번 도서관 (Java) (0) | 2025.06.25 |
[백준] 20061번 모노미노도미노2 (Java) (1) | 2025.03.01 |
[백준] 19237번 어른 상어 (Java) (0) | 2025.02.25 |