백준 7562번: 나이트의 이동

이 문제는 4 * 4  체스판을 직접 그려보고 한 시작점에서 모든 칸을 몇 칸 안에 도달할 수 있는지 직접 구해본다면 접근 방법을 찾을 수 있다.

 

다음은 4 * 4 체스판의 (0,0)에서 출발 했을 때 모든 칸에 도달하는 최소 이동 횟수다.

만약 (3,2) 칸에 몇 번만에 도달하는지 알고 싶다면 체스판을 그래프화 하여  graph[3][2]의 값을 구하면 된다.

 

다음은 손 코딩으로 흐름을 나타낸 것이다.

 

다음은 정답 java 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int whereIs(int x, int y, int[][] graph, int end_x, int end_y) {
		
		int[] dx = {-1, 1, 2, -2, 2, 1, -2, -1};
		int[] dy = {2, 2, 1, 1, -1, -2, -1, -2};
		
		Queue<int[]> queue = new LinkedList<int[]>();
		int[] list = {x,y};
		queue.add(list);
		
		while(queue.size()!=0) {
			int[] data = queue.poll();
			int cur_i = data[0];
			int cur_j = data[1];
			for(int r=0; r<8; r++) {
				int next_i = cur_i + dx[r];
				int next_j = cur_j + dy[r];
				
				if(next_i>=0 && next_i<graph.length && next_j>=0 && next_j<graph[0].length) {
					if(graph[next_i][next_j] < 0) {
						graph[next_i][next_j] = graph[cur_i][cur_j]+1;
						int[] next_list = {next_i, next_j};
						queue.add(next_list);
					}
				}
			}
		}
		return graph[end_x][end_y];
	}
	
	public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	     StringTokenizer st = new StringTokenizer(br.readLine());
	     StringBuilder sb = new StringBuilder();
	     
	     int n = Integer.parseInt(st.nextToken());
	     
	     for(int i=0; i<n; i++) {
	    	 st = new StringTokenizer(br.readLine());
	    	 int k = Integer.parseInt(st.nextToken());  //k * k
	    	 
	    	 int[][] graph = new int[k][k];  //초기화값 = 0
	    	 
	    	 for(int j=0; j<k; j++) {
	    		 for(int p=0; p<k; p++) {
	    			 graph[j][p] = -1;
	    		 }
	    	 }
	    	 
	    	 st = new StringTokenizer(br.readLine());
	    	 
	    	 int x = Integer.parseInt(st.nextToken());
	    	 int y = Integer.parseInt(st.nextToken());
	    	 
	    	 graph[x][y] = 0;
	    	 
	    	 st = new StringTokenizer(br.readLine());
	    	 int end_x = Integer.parseInt(st.nextToken());
	    	 int end_y = Integer.parseInt(st.nextToken());
	    	 
	    	 sb.append(whereIs(x, y, graph, end_x, end_y)+"\n");
	    	 
	     }
	     
	     bw.write(sb.toString());
	     bw.flush();
	     bw.close();
	}

}