백준 [1726] 로봇
문제보기
풀이
- bfs
- 주의사항
- 아래에서 break가 아닌 continue
if (visited[d][x][y] != 0 && visited[d][x][y] <= command + 1)
continue;
- 2번의 명령으로 180도 회전할 수 있다.
- 인덱스 실수 주의
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, ans;
static int[][] map;
static int[][] station;
static int[] dx = { 0, 0, 1, -1 }; // 동서남북
static int[] dy = { 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());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
station = new int[2][3];
ans = 987654321;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
station[i][j] = Integer.parseInt(st.nextToken()) - 1;
}
}
move();
System.out.println(ans);
}
public static void move() {
Queue<int[]> queue = new LinkedList<>();
int[][][] visited = new int[4][N][M];
queue.add(new int[] { station[0][0], station[0][1], station[0][2], 0 });
while (!queue.isEmpty()) {
int[] q = queue.poll();
if (q[3] >= ans)
continue;
if (q[0] == station[1][0] && q[1] == station[1][1]) {
if (q[2] == station[1][2]) {
ans = Math.min(ans, q[3]);
} else {
boolean flag = false;
if (q[2] == 0 && station[0][2] == 1) {
flag = true;
} else if (q[2] == 1 && station[0][2] == 0) {
flag = true;
} else if (q[2] == 2 && station[0][2] == 3) {
flag = true;
} else if (q[2] == 3 && station[0][2] == 2) {
flag = true;
}
if (flag)
q[3]++;
ans = Math.min(ans, q[3] + 1);
}
continue;
}
for (int d = 0; d < 4; d++) {
for (int k = 1; k <= 3; k++) {
int x = q[0] + (dx[d] * k);
int y = q[1] + (dy[d] * k);
boolean chk = false;
if (isRange(x, y) && map[x][y] == 0) {
int command = q[3];
if (q[2] != d) {
if (q[2] == 0 && d == 1)
command += 2;
else if (q[2] == 1 && d == 0)
command += 2;
else if (q[2] == 2 && d == 3)
command += 2;
else if (q[2] == 3 && d == 2)
command += 2;
else
command++;
}
if (visited[d][x][y] != 0 && visited[d][x][y] <= command + 1)
continue;
if (command + 1 >= ans)
break;
queue.add(new int[] { x, y, d, command + 1 });
visited[d][x][y] = command + 1;
chk = true;
}
if (!chk)
break;
}
}
}
}
public static boolean isRange(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < M;
}
}