문제
M x N 격자에서 로봇이 시작 위치/방향에서 목표 위치/방향까지 이동할 때, 명령(전진 1~3칸 또는 좌/우 회전)의 최소 횟수를 구하라.
입력
첫째 줄에 M, N, 이후 M줄에 격자(0: 빈 칸, 1: 벽), 마지막 두 줄에 시작과 목표의 행, 열, 방향이 주어진다.
출력
최소 명령 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 6 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 4 2 3 2 4 1 | 9 |
풀이
BFS로 (행, 열, 방향) 상태를 탐색하며 전진과 회전 명령의 최소 횟수를 구한다.
- 상태를 (행, 열, 방향)으로 정의하고 3차원 visited 배열로 방문 체크한다
- 현재 방향으로 1~3칸 전진을 시도하되, 벽이 있으면 더 이상 진행하지 않는다
- 4방향 중 현재와 다른 방향으로 회전하며, 반대 방향이면 2번 회전이 필요하다
- 목표 상태에 도달하면 명령 횟수를 출력한다
핵심 아이디어: 위치와 방향을 합친 상태 공간에서 BFS를 수행하면 최소 명령 횟수를 보장한다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day724BOJ1726로봇 {
static int M;
static int N;
static int[][] map;
static boolean[][][] visited;
static Robot start;
static Robot finish;
static int[] dx = { 0, 0, 1, -1 }; // 동, 서, 남, 북
static int[] dy = { 1, -1, 0, 0 };
public static void main(String[] args) throws Exception {
init();
bfs();
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[M + 1][N + 1];
visited = new boolean[M + 1][N + 1][5];
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
start = new Robot(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
0);
st = new StringTokenizer(br.readLine());
finish = new Robot(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
0);
}
static void bfs() {
Queue<Robot> q = new LinkedList<>();
visited[start.x][start.y][start.dir] = true;
q.add(start);
while (!q.isEmpty()) {
Robot r = q.poll();
int x = r.x;
int y = r.y;
int dir = r.dir;
int count = r.count;
if (x == finish.x && y == finish.y && dir == finish.dir) {
System.out.println(count);
return;
}
for (int i = 1; i <= 3; i++) {
int nx = x + (dx[dir - 1] * i);
int ny = y + (dy[dir - 1] * i);
if (nx <= 0 || ny <= 0 || nx > M || ny > N)
continue;
if (map[nx][ny] == 0) {
if (!visited[nx][ny][dir]) {
visited[nx][ny][dir] = true;
q.add(new Robot(nx, ny, dir, count + 1));
}
} else {
break;
}
}
for (int i = 1; i <= 4; i++) {
if (dir != i && !visited[x][y][i]) {
int turn = 1;
if (dir == 1) {
if (i == 2) {
turn++;
}
} else if (dir == 2) {
if (i == 1) {
turn++;
}
} else if (dir == 3) {
if (i == 4) {
turn++;
}
} else {
if (i == 3) {
turn++;
}
}
visited[x][y][i] = true;
q.add(new Robot(x, y, i, count + turn));
}
}
}
}
static class Robot {
int x;
int y;
int dir;
int count;
public Robot(int x, int y, int dir, int count) {
this.x = x;
this.y = y;
this.dir = dir;
this.count = count;
}
}
}복잡도
- 시간: O(M * N * 4)
- 공간: O(M * N * 4)