https://www.acmicpc.net/problem/16959
16959번: 체스판 여행 1
크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트,
www.acmicpc.net
[풀이]
BFS 문제이다.
말은 1에서 시작해서 N^2-1 까지 차례대로 밟아가며 이동해야한다.
차례대로 숫자가 1씩 늘어나면서 방문해야 하기 때문에 말은 현재 자신이 방문한 숫자 정보를 가지고 있어야 한다.
중간에 다른 숫자가 적혀있는 부분도 거쳐갈 수 있기 때문에 자신이 다음에 방문해야 할 숫자가 아니면 원래 말이 가지고 있던 숫자 정보를 그대로 가지고 간다.
현재 말이 가지고 있는 숫자 정보보다 1 큰 숫자가 적혀있는 칸에 방문하면 숫자 정보를 갱신해준다.
한 위치에서 말의 정보는 ( Y좌표, X좌표. 현재 가지고 있는 숫자 정보, 말 종류 ) 로 나타낼 수 있다.
위의 정보를 가지고 visit 체크를 하면 중복 없이 가장 시간이 적게 걸리는 경우들을 큐에 넣을 수 있다.
1 |
9 |
3 |
8 |
6 |
7 |
4 |
2 |
5 |
1에서 비숍으로 1초후에 갈 수 있는 경로들은 주황색 글씨로 칠해진 부분이다.
큐에 주황색 글씨로 칠해진 부분을 모두 넣어주고, 나이트, 룩일 경우도 모두 넣어준다.
또한, 말을 바꾸는 행동도 할 수 있으므로 말을 바꾸는 경우도 큐에 넣어준다.
이렇게 BFS를 진행하면서 큐에서 뺀 노드의 숫자 정보가 8이고, 다음 방문하는 곳이 9인 경우 시간을 리턴해준다.
[소스코드]
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main { // bj16959 체스판 여행1
/*
* 0나이트 1비숍 2룩
*/
static int n;
static int[][] arr;
static int[] nightX= {1,2,2,1,-1,-2,-2,-1};
static int[] nightY= {-2,-1,1,2,2,1,-1,-2};
static int[] bishopX= {1,1,-1,-1};
static int[] bishopY= {-1,1,1,-1};
static int[] rookX= {0,1,0,-1};
static int[] rookY= {-1,0,1,0};
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
arr=new int[n][n];
int sy=0;
int sx=0;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
arr[i][j]=sc.nextInt();
if(arr[i][j]==1) {
sy=i;
sx=j;
}
}
}
int snum=1;
int min=go(sy,sx,snum);
System.out.println(min);
}
public static int go(int sy,int sx,int snum) {
int min=9999;
boolean[][][][] chk=new boolean[n][n][n*n+1][3];
Queue<int[]> q=new LinkedList<>();
int[] start= {sy,sx,snum,0,0};
q.add(start);
chk[sy][sx][snum][0]=true;
int[] start2= {sy,sx,snum,1,0};
q.add(start2);
chk[sy][sx][snum][1]=true;
int[] start3= {sy,sx,snum,2,0};
chk[sy][sx][snum][2]=true;
q.add(start3);
while(!q.isEmpty()) {
int[] temp=q.remove();
int y=temp[0];
int x=temp[1];
int num=temp[2];
int mal=temp[3];
int time=temp[4];
if(arr[y][x]==num+1) num++;
if(num==n*n) {
return time;
}
for(int k=1;k<=2;k++) {
if(!chk[y][x][num][(mal+k)%3]) {
chk[y][x][num][(mal+k)%3]=true;
int[] nnext= {y,x,num,(mal+k)%3,time+1};
q.add(nnext);
}
}
if(mal==0) { // 나이트
for(int d=0;d<8;d++) {
int ty=y+nightY[d];
int tx=x+nightX[d];
if(ty<0||ty>=n||tx<0||tx>=n) continue;
if(chk[ty][tx][num][mal]) continue;
chk[ty][tx][num][mal]=true;
int[] next= {ty,tx,num,mal,time+1};
q.add(next);
}
}
else if(mal==1) { // 비숍
for(int d=0;d<4;d++) {
int dis=1;
while(true) {
int ty=y+bishopY[d]*dis;
int tx=x+bishopX[d]*dis;
if(ty<0||ty>=n||tx<0||tx>=n) break;
if(chk[ty][tx][num][mal]) {
dis++;
continue;
}
chk[ty][tx][num][mal]=true;
int[] next= {ty,tx,num,mal,time+1};
q.add(next);
dis++;
}
}
}
else if(mal==2) { // 룩
for(int d=0;d<4;d++) {
int dis=1;
while(true) {
int ty=y+rookY[d]*dis;
int tx=x+rookX[d]*dis;
if(ty<0||ty>=n||tx<0||tx>=n) break;
if(chk[ty][tx][num][mal]) {
dis++;
continue;
}
chk[ty][tx][num][mal]=true;
int[] next= {ty,tx,num,mal,time+1};
q.add(next);
dis++;
}
}
}
}
return min;
}
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
백준 17070번 - 파이프 옮기기 1 (0) | 2020.11.17 |
---|---|
백준 16235번 - 나무 재테크 (0) | 2020.11.17 |
백준 1562번 - 계단 수 (0) | 2020.11.17 |
백준 10164번 - 격자상의 경로 (0) | 2020.11.17 |
백준 2188번 - 축사배정 (0) | 2020.11.16 |