OJ
[BOJ] 1726 로봇 (JAVA)
P3PP4
2022. 12. 26. 11:32
https://www.acmicpc.net/problem/1726
1726번: 로봇
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는
www.acmicpc.net
BFS로 해결할 수 있는 문제입니다.
st = new StringTokenizer(br.readLine(), " ");
sr = Integer.parseInt(st.nextToken());
sc = Integer.parseInt(st.nextToken());
sd = Integer.parseInt(st.nextToken());
if(sd == 2) sd = 3;
else if(sd == 3) sd = 2;
else if(sd == 4) sd = 0;
st = new StringTokenizer(br.readLine(), " ");
er = Integer.parseInt(st.nextToken());
ec = Integer.parseInt(st.nextToken());
ed = Integer.parseInt(st.nextToken());
if(ed == 2) ed = 3;
else if(ed == 3) ed = 2;
else if(ed == 4) ed = 0;로봇의 방향에 대해서 저에게 편한 방법으로 풀려고 값을 조금 수정했습니다.
동 서 남 북 -> 북 동 남 서(시계방향)
for (int i = 0; i < N + 2; i++) {
map[i][0] = map[i][M + 1] = 1;
}
for (int i = 0; i < M + 2; i++) {
map[0][i] = map[N + 1][i] = 1;
}또한 배열의 테두리를 1로 채웠습니다.
이문제에서 중요하다고 생각하는 부분
1. 앞으로 전진할 때 벽이 나오면 그 다음 칸은 보지 않고 넘긴다.
2. 행, 열 위치에 추가로 방향에 대한 visited 체크를 한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M, sr, sc, sd, er, ec, ed;
static int[][] map;
static int[][][] visited;
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N + 2][M + 2];
visited = new int[4][N + 2][M + 2];
for (int i = 0; i < N + 2; i++) {
map[i][0] = map[i][M + 1] = 1;
}
for (int i = 0; i < M + 2; i++) {
map[0][i] = map[N + 1][i] = 1;
}
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine(), " ");
sr = Integer.parseInt(st.nextToken());
sc = Integer.parseInt(st.nextToken());
sd = Integer.parseInt(st.nextToken());
if(sd == 2) sd = 3;
else if(sd == 3) sd = 2;
else if(sd == 4) sd = 0;
st = new StringTokenizer(br.readLine(), " ");
er = Integer.parseInt(st.nextToken());
ec = Integer.parseInt(st.nextToken());
ed = Integer.parseInt(st.nextToken());
if(ed == 2) ed = 3;
else if(ed == 3) ed = 2;
else if(ed == 4) ed = 0;
// end of input
Queue<Robot> q = new LinkedList<>();
q.offer(new Robot(sr, sc, sd));
visited[sd][sr][sc] = 1;
while(!q.isEmpty()) {
Robot r = q.poll();
if(r.r == er && r.c == ec && r.d == ed) {
System.out.print(visited[ed][er][ec] - 1);
return;
}
// 오른쪽 회전
if(visited[(r.d + 1) % 4][r.r][r.c] == 0) {
q.offer(new Robot(r.r, r.c, (r.d + 1) % 4));
visited[(r.d + 1) % 4][r.r][r.c] = visited[r.d][r.r][r.c] + 1;
}
// 왼쪽 회전
if(visited[r.d - 1 < 0 ? r.d + 3 : r.d - 1][r.r][r.c] == 0) {
q.offer(new Robot(r.r, r.c, r.d - 1 < 0 ? r.d + 3 : r.d - 1));
visited[r.d - 1 < 0 ? r.d + 3 : r.d - 1][r.r][r.c] = visited[r.d][r.r][r.c] + 1;
}
// 앞으로 i칸 전진
for (int i = 1; i <= 3; i++) {
int nr = r.r + dr[r.d] * i;
int nc = r.c + dc[r.d] * i;
if(visited[r.d][nr][nc] == 0) {
if(map[nr][nc] == 1) break;
q.offer(new Robot(nr, nc, r.d));
visited[r.d][nr][nc] = visited[r.d][r.r][r.c] + 1;
}
}
}
}
static class Robot {
int r, c, d;
public Robot(int r, int c, int d) {
this.r = r;
this.c = c;
this.d = d;
}
}
}