백준 16959번 - 체스판 여행

https://www.acmicpc.net/problem/16959

16959번: 체스판 여행 1

 

[풀이]

​

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;
	}
}