OJ
[BOJ] 16959 체스판 여행 1 (JAVA)
P3PP4
2023. 1. 23. 10:00
https://www.acmicpc.net/problem/16959
16959번: 체스판 여행 1
크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트,
www.acmicpc.net
1 -> 2 -> ... -> N * N까지 순서대로 체스판을 밟으면서 BFS를 진행해야 합니다.
(어떤 체스말로 이동할 건지, 최근에 밟은 숫자가 몇 번인지, 행, 열) 네 가지를 모두 신경써야 하기 때문에 visited 배열을 4차원 배열로 선언했습니다.
visited = new int[3][N * N + 1][N][N];
체스말은 나이트, 비숍, 룩 세 가지가 있기 때문에 dr, dc를 16칸 짜리 배열로 만들었습니다.
0~7 나이트, 8~11 비숍, 12~15 룩의 이동입니다.
static int[] dr = { -2, -1, 1, 2, 2, 1, -1, -2, -1, 1, 1, -1, -1, 0, 1, 0 };
static int[] dc = { 1, 2, 2, 1, -1, -2, -2, -1, 1, 1, -1, -1, 0, 1, 0, -1 };
시작할 때는 나이트, 비숍, 룩 모두 놓고 시작해도 되기 때문에 Queue에 세 가지 모두 넣은 상태로 시작했습니다.
Pos의 state가 0일 때 나이트, 1일 때 비숍, 2일 때 룩입니다.
Queue<Pos> q = new LinkedList<>();
q.offer(new Pos(sr, sc, 0, 1));
q.offer(new Pos(sr, sc, 1, 1));
q.offer(new Pos(sr, sc, 2, 1));
visited[0][1][sr][sc] = 1;
visited[1][1][sr][sc] = 1;
visited[2][1][sr][sc] = 1;
마지막 숫자(N * N)을 밟으면 종료 조건이 되고,
다음 숫자를 밟으면 그 다음 숫자를 목표로 BFS를 수행하도록 Queue에 다시 넣어줬습니다.
// 종료 조건
if(map[p.row][p.col] == NN && p.num + 1 == NN) {
System.out.println(visited[p.state][NN - 1][p.row][p.col] - 1);
return;
// 다음 숫자에 위치
} else if(map[p.row][p.col] == p.num + 1) {
q.offer(new Pos(p.row, p.col, p.state, p.num + 1));
visited[p.state][p.num + 1][p.row][p.col] = visited[p.state][p.num][p.row][p.col];
}
제자리에서 체스말을 바꿀 때 1초가 소요됩니다.
// 제자리에서 말 바꾸기
for (int i = 0; i < 3; i++) {
if(visited[i][p.num][p.row][p.col] == 0) {
q.offer(new Pos(p.row, p.col, i, p.num));
visited[i][p.num][p.row][p.col] = visited[p.state][p.num][p.row][p.col] + 1;
}
}
코드가 좀 더 간결해지도록 손 볼 수 있지 않을까요?
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, NN, sr, sc;
static int[][] map;
static int[][][][] visited;
static int[] dr = { -2, -1, 1, 2, 2, 1, -1, -2, -1, 1, 1, -1, -1, 0, 1, 0 };
static int[] dc = { 1, 2, 2, 1, -1, -2, -2, -1, 1, 1, -1, -1, 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
N = Integer.parseInt(br.readLine());
NN = N * N;
map = new int[N][N];
visited = new int[3][N * N + 1][N][N];
sr = 0;
sc = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 1) {
sr = i;
sc = j;
}
}
} // end of input
Queue<Pos> q = new LinkedList<>();
q.offer(new Pos(sr, sc, 0, 1));
q.offer(new Pos(sr, sc, 1, 1));
q.offer(new Pos(sr, sc, 2, 1));
visited[0][1][sr][sc] = 1;
visited[1][1][sr][sc] = 1;
visited[2][1][sr][sc] = 1;
while(!q.isEmpty()) {
Pos p = q.poll();
// 종료 조건
if(map[p.row][p.col] == NN && p.num + 1 == NN) {
System.out.println(visited[p.state][NN - 1][p.row][p.col] - 1);
return;
// 다음 숫자에 위치
} else if(map[p.row][p.col] == p.num + 1) {
q.offer(new Pos(p.row, p.col, p.state, p.num + 1));
visited[p.state][p.num + 1][p.row][p.col] = visited[p.state][p.num][p.row][p.col];
}
// 제자리에서 말 바꾸기
for (int i = 0; i < 3; i++) {
if(visited[i][p.num][p.row][p.col] == 0) {
q.offer(new Pos(p.row, p.col, i, p.num));
visited[i][p.num][p.row][p.col] = visited[p.state][p.num][p.row][p.col] + 1;
}
}
// 나이트일 때 이동
if(p.state == 0) {
for (int dir = 0; dir < 8; dir++) {
int nr = p.row + dr[dir];
int nc = p.col + dc[dir];
if(0 <= nr && nr < N && 0 <= nc && nc < N && visited[p.state][p.num][nr][nc] == 0) {
q.offer(new Pos(nr, nc, p.state, p.num));
visited[p.state][p.num][nr][nc] = visited[p.state][p.num][p.row][p.col] + 1;
}
}
// 비숍이나 룩일 때 이동
} else {
for (int dir = 8; dir < 16; dir++) {
if(p.state == 1 && 11 < dir) break;
else if(p.state == 2 && dir < 12) continue;
int nr = p.row + dr[dir];
int nc = p.col + dc[dir];
while(0 <= nr && nr < N && 0 <= nc && nc < N) {
if(visited[p.state][p.num][nr][nc] == 0) {
q.offer(new Pos(nr, nc, p.state, p.num));
visited[p.state][p.num][nr][nc] = visited[p.state][p.num][p.row][p.col] + 1;
}
nr += dr[dir];
nc += dc[dir];
}
}
}
}
}
static class Pos {
int row, col, state, num;
public Pos(int row, int col, int state, int num) {
this.row = row;
this.col = col;
this.state = state;
this.num = num;
}
}
}