본문 바로가기

Dot Algo∙ DS/PS

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

    #7562 나이트의 이동

    난이도 : 실버 2

    유형 : 그래프 탐색

     

    7562번: 나이트의 이동

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

    www.acmicpc.net

    ▸ 문제

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

     입력

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

    각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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;
    	}
    	
    	
    }