[BOJ 16959] 체스판 여행 1 (Java)

BOJ 16959 체스판 여행 1

문제풀이

풀이는 이 문서를 참조하였습니다.

기본적으로 BFS의 개념으로 풀이하는 문제지만 이런 문제들은 방문할 때의 상태를 추가함으로써 난이도를 상승시킨다. 이 문제에서는

• 좌표
• 말의 종류
• 도착한 시간
• 어떤 목표를 향해 나아가고 있느지

의 상태를 저장함으로써 문제의 조건을 모두 만족시킬 수 있다. 같은 좌표에 존재하더라도 달라질 수 있는 상태들에 대해서 잘 파악하고 그에 따른 방문체크를 수행해주는 것이 고난도 BFS 문제의 핵심인것 같다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static class Node {
		int r, c, type, time, next;

		Node(int r, int c, int type, int time, int next) {
			this.r = r;
			this.c = c;
			this.type = type;
			this.time = time;
			this.next = next;
		}
	}

	static int[][][] dir = { { { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } },
			{ { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 } },
			{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }, };

	static final int BISHOP = 0;
	static final int KNIGHT = 1;
	static final int ROOK = 2;

	static Queue<Node> q;
	static int[][] map;
	static boolean[][][][] visited;
	static int N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		q = new LinkedList<>();
		map = new int[N][N];
		visited = new boolean[N][N][3][N * N + 1];

		for (int r = 0; r < N; ++r) {
			String[] line = br.readLine().split(" ");
			for (int c = 0; c < N; ++c) {
				map[r][c] = Integer.parseInt(line[c]);

				if (map[r][c] == 1) {
					for (int i = 0; i < 3; ++i) {
						q.offer(new Node(r, c, i, 0, 2));
						visited[r][c][i][2] = true;
					}
				}
			}
		}

		System.out.println(bfs());
	}

	private static int bfs() {
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(cur.next == N * N + 1) {
				return cur.time;
			}
			
			// 말 바꾸기
			for(int i = 0 ; i < 3 ; ++i) {
				if(cur.type == i || visited[cur.r][cur.c][i][cur.next]) continue;
				
				q.offer(new Node(cur.r, cur.c, i, cur.time + 1, cur.next));
				visited[cur.r][cur.c][i][cur.next] = true;
			}
			
			// 말 옮기기 
			switch(cur.type) {
			case BISHOP:
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = cur.r + dir[BISHOP][d][0];
					int nc = cur.c + dir[BISHOP][d][1];
					
					while(nr >= 0 && nr < N && nc >= 0 && nc < N) {
						if(!visited[nr][nc][BISHOP][cur.next]) {
							visited[nr][nc][BISHOP][cur.next] = true;
							
							if(map[nr][nc] == cur.next) {
								q.offer(new Node(nr, nc, BISHOP, cur.time + 1, cur.next + 1));
							} else {
								q.offer(new Node(nr, nc, BISHOP, cur.time + 1, cur.next));
							}
						}
						
						nr += dir[BISHOP][d][0];
						nc += dir[BISHOP][d][1];
					}
				}
				break;
				
			case KNIGHT:
				for(int d = 0 ; d < 8 ; ++d) {
					int nr = cur.r + dir[KNIGHT][d][0];
					int nc = cur.c + dir[KNIGHT][d][1];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc][KNIGHT][cur.next]) continue;
						
					visited[nr][nc][KNIGHT][cur.next] = true;
					
					if(map[nr][nc] == cur.next) {
						q.offer(new Node(nr, nc, KNIGHT, cur.time + 1, cur.next + 1));
					} else {
						q.offer(new Node(nr, nc, KNIGHT, cur.time + 1, cur.next));
					}
				}
				break;
				
			case ROOK:
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = cur.r + dir[ROOK][d][0];
					int nc = cur.c + dir[ROOK][d][1];
					
					while(nr >= 0 && nr < N && nc >= 0 && nc < N) {
						if(!visited[nr][nc][ROOK][cur.next]) {
							visited[nr][nc][ROOK][cur.next] = true;
							
							if(map[nr][nc] == cur.next) {
								q.offer(new Node(nr, nc, ROOK, cur.time + 1, cur.next + 1));
							} else {
								q.offer(new Node(nr, nc, ROOK, cur.time + 1, cur.next));
							}
						}
						
						nr += dir[ROOK][d][0];
						nc += dir[ROOK][d][1];
					}
				}
				break;
				
			}
		}
		
		return -1;
	}
}