백준 1600 - 말이 되고픈 원숭이
Updated:
Java
1600 번 - 말이 되고픈 원숭이
문제
말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 참고로 말은 장애물을 뛰어넘을 수 있다.
원숭이는 능력이 부족해서 총 K번만 말(나이트)와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.
이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다.
인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다.
격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.
접근 방법
0,0에서 n-1,m-1까지 이동하여, 그 이동 횟수를 탐색하는 BFS 문제이다.
여기서 k번의 다른 이동 패턴이 주어졌다.
원숭이가 점프를 하였는지 하지 않았는지의 상태를 나타내기 위해, 1차원을 더하여 총 3차원을 배열로 나타내었다.
해당 좌표까지 원숭이가 몇번 이동하여 도착하였는가를 나타내는 3차원 배열로 이동횟수[남은 점프 횟수][y좌표][x좌표]로 두었다.
각 점에서 점프를 하지 않을 경우인 상,하,좌,우 탐색하고, k번 점프 횟수가 0보다 크면, 말의 이동 패턴에 따라 갈 수 있는 지점으로 이동한다.
각 좌표에 먼저 도착한 이동 횟수를 기록하고, 다른 queue에서 이동하는 경우를 막기 위해 visited[][][]배열을 선언하였다.
뒤늦게 도착한 경우, 이동 횟수는 처음 도착했을 때 보다 더 늦기 때문에, dp를 사용하지 않아도 된다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, result = Integer.MAX_VALUE, k;
static int[][] board;
static int[][][] move;
static boolean visited[][][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
k = stoi(br.readLine());
stk = new StringTokenizer(br.readLine());
m = stoi(stk.nextToken());
n = stoi(stk.nextToken());
board = new int[n][m];
move = new int[k + 1][n][m];
visited = new boolean[k+1][n][m];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for(int j = 0; j < m; j++) {
board[i][j] = stoi(stk.nextToken());
}
}
for(int i = 0; i < k + 1; i++) {
visited[i][0][0] = true;
}
bfs();
for(int i = 0; i < k + 1; i++) {
if(visited[i][n-1][m-1]) {
result = Math.min(result, move[i][n-1][m-1]);
}
}
if(result != Integer.MAX_VALUE)
System.out.println(result);
else
System.out.println(-1);
br.close();
}
// 우 하 상 좌
static int[] dy = {0, 1, -1, 0};
static int[] dx = {1, 0, 0, -1};
// 말이 점프하는 방향, 숫자는 점프 위치가 시계 방향으로 나타내었을 때, 1~8
// 3 4 1 2 5 6 7 8
static int[] hy = {1, 2, -2, -1, 2, 1, -1, -2};
static int[] hx = {2, 1, 1, 2, -1, -2, -2, -1};
static void bfs() {
Queue<Point> q = new LinkedList<>();
q.add(new Point(k, 0, 0));
// lv은 몇 번째 움직임인지 나타냄
int y, x, z, ny, nx, find = 1, cnt = 0, lv = 1;
while(!q.isEmpty()) {
// 몇 번째의 움직임인지 나타내기 위한 반복문
while(find-- != 0) {
Point p = q.poll();
y = p.y;
x = p.x;
z = p.z;
for(int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if(isIn(ny,nx) && board[ny][nx] != 1 && !visited[z][ny][nx]) {
move[z][ny][nx] = lv;
visited[z][ny][nx] = true;
q.add(new Point(z, ny, nx));
cnt++;
}
}
// 말 점프
if(z > 0) {
for(int i = 0; i < 8; i++) {
ny = y + hy[i];
nx = x + hx[i];
if(isIn(ny,nx) && board[ny][nx] != 1 && !visited[z-1][ny][nx]) {
move[z - 1][ny][nx] = lv;
visited[z - 1][ny][nx] = true;
q.add(new Point(z - 1, ny, nx));
cnt++;
}
}
}
}
lv++; // 다음 움직임
find = cnt;
cnt = 0;
}
}
// 주어진 범위 안에 있는가
public static boolean isIn(int y, int x){
if(y < 0 || y >= n || x < 0 || x >= m)
return false;
return true;
}
static class Point{
int z,y,x;
public Point(int z, int y, int x) {
super();
this.z = z;
this.y = y;
this.x = x;
}
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
벽 부수고 이동하기와 비슷한 문제였다.
각 상태를 표현하는 차원을 고려하는 법을 생각해야 한다.
