백준 - 1600번 말이 되고픈 원숭이

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

참고하게된 블로그
https://simju9397.tistory.com/25

접근법

처음에는 DFS로 풀이를 하였는데, 메모리초과가 나옴. 전체탐색하는 방법으로 생각해서 그런건데 잘못접근하여서
BFS로 바꿈.

1. Point객체는 좌표 x, y와 이동한 횟수, 말처럼이동한 횟수를 가짐
2. Dir배열은 0~7은 말처럼 이동하는 경우의 좌표이고, 8~11은 일반 상하좌우 이동
3. 일반 BFS처럼 Queue 생성해서 방문여부 체크하며 진행하는데, 여기서 시간초과나오고 했던 부분이 있음

   Visit x, y, z 배열의 의미가 중요한데, '말처럼 Z번 움직여서 X, Y좌표에 방문하였는가?'를 의미함

3-1. Z는 0번부터 K번까지이므로 크기는 K+1 짜리 3차원 배열이어야함
3-2. 나머지는 일반 BFS와 동일하게 갈 수 있는지 없는지 체크

소스

import java.io.*;
import java.util.*;

public class Main {
	static int K;
	static int W, H;
	static int[][] Board;
	static int[][] Dir = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
							{2, 1}, {1, 2}, {-1, 2}, {-2, 1},
							{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	static boolean[][][] Visit;
	static int Answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		K = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		Board = new int[H][W];
		Visit = new boolean[H][W][K+1]; // x, y 좌표로 이동하는데 k 말처럼 이동하여 방문하였는지 체크
		for(int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < W; j++) {
				Board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		bfs();
		if(Answer == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(Answer);
	}
	static void bfs() {
		Queue<Point_b1600> q = new LinkedList<Point_b1600>();
		q.offer(new Point_b1600(0, 0, 0, 0));
		Visit[0][0][0] = true; //0, 0은 말처럼 0번 움직여서 방문한거
		
		while(!q.isEmpty()) {
			Point_b1600 cur = q.poll();
			int cx = cur.x;
			int cy = cur.y;
			int cMcnt = cur.moveCnt;
			int cNcnt = cur.nightCnt;
			
			if(cx == H-1 && cy == W-1) {
				Answer = cMcnt < Answer ? cMcnt : Answer; 
			}
			
			int loopCnt = cNcnt < K ? 0 : 8;
			
			for(int i = loopCnt; i < Dir.length; i++) {
				int nx = cx + Dir[i][0];
				int ny = cy + Dir[i][1];
				
				//범위밖이면 바로 패스
				if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
				
				//범위 내인데, X면 못감.
				if(Board[nx][ny] == 1) continue;
				
				boolean isNightMove = i < 8 ? true : false; //0~7이면 말처럼 이동이고, 8~11이면 일반 이동
				
				// 해당 좌표에 말처럼 움직이는데, 방문한적이 없으면 방문
				if(isNightMove && !Visit[nx][ny][cNcnt+1]) {
					//방문처리해주고, q에 offer
					Visit[nx][ny][cNcnt+1] = true;
					q.offer(new Point_b1600(nx, ny, cMcnt+1, cNcnt+1));
				} 
				// 해당 좌표에 말처럼 움직이지 않았는데, 방문한적이 없으면 방문
				else if(!isNightMove && !Visit[nx][ny][cNcnt]) {
					Visit[nx][ny][cNcnt] = true;
					q.offer(new Point_b1600(nx, ny, cMcnt+1, cNcnt));
				}
			}
		}		
	}
}

class Point_b1600{
	int x;
	int y;
	int moveCnt;
	int nightCnt;
	Point_b1600(int x, int y, int moveCnt, int nightCnt){
		this.x = x;
		this.y = y;
		this.moveCnt = moveCnt;
		this.nightCnt = nightCnt;
	}
}