[BOJ] 백준 7562번 나이트의 이동 (Java)

#7562 나이트의 이동

난이도 : 실버 2

유형 : 그래프 탐색

7562번: 나이트의 이동

▸ 문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

▸ 입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

▸ 출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

 

 

 

 

문제 풀이 🖋  

해당 문제는 나이트 이동 방향 8가지의 경우를 모두 BFS 탐색해주면 된다.

 

📚  조건

  ∙ 체스판 한 변의 길이 l (4<= l <= 300)

  ∙ 체스판의 크기 | x |

  ∙ 체스팍 각 칸은 두수의 쌍  {0, ..., l-1} × {0, ..., l-1}으로 나타낸다.

  ∙ 이동방향 총 8가지

    → dx = {-2, -1, 2, 1, 2, 1, -2, -1}

    → dy = {1, 2, 1, 2, -1, -2, -1, -2}

 

 

 

풀이 코드 ✔︎ 

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

public class Main {
	
	static int[] dx = {-2,-1,2,1,2,1,-2,-1};
	static int[] dy = {1,2,1,2,-1,-2,-1,-2};
	static boolean[][] visited;
	static int[][] memo;
	static int len;
	static int e_x, e_y;
	static Queue<Pos> q = new LinkedList<>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		
		
		for(int t=0; t<tc; t++) {
			len = Integer.parseInt(br.readLine());
			memo = new int[len][len];
			visited = new boolean[len][len];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s_x = Integer.parseInt(st.nextToken());
			int s_y = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			e_x = Integer.parseInt(st.nextToken());
			e_y = Integer.parseInt(st.nextToken());
			
			bfs(new Pos(s_x, s_y));
			System.out.println(memo[e_x][e_y]);
			
		}
	}
	
	 static void bfs(Pos nPos) {
	        if(nPos.x == e_x && nPos.y == e_y) {
	            return;
	        }
	        visited[nPos.x][nPos.y] = true;
	        
	        q.add(nPos);
	        
	        while(!q.isEmpty()) {
	            Pos p = q.poll();
	            int x = p.x;
	            int y = p.y;
	            
	            for(int i=0; i<dx.length; i++) {
	                int nx = x + dx[i];
	                int ny = y + dy[i];
	                
	                if(nx>=0 && nx<len && ny>=0 && ny<len && !visited[nx][ny]) {
	                    q.add(new Pos(nx,ny));
	                    visited[nx][ny] = true;
	                    //전의 이동 횟수에 +1 씩 더해주며 이동 횟수를 증가시켜준다.
	                    memo[nx][ny] = memo[x][y] + 1;
	                }
	            }
	        }
	        
	    }
}

class Pos{
	int x;
	int y;
	public Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	
}