99클럽 코테 스터디 9일차 TIL + 백준 나이트의 이동

 

 

문제

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

 

 

 

입력

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

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

 

출력

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

 

 

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

class Point {
    int x, y, count;
    
    Point(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}

public class Main {
    // 나이트가 이동할 수 있는 8가지 방향
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); 
        
        for (int t = 0; t < T; t++) {
            int l = Integer.parseInt(br.readLine());  
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            int endX = Integer.parseInt(st.nextToken());
            int endY = Integer.parseInt(st.nextToken());
            
            System.out.println(bfs(l, startX, startY, endX, endY));
        }
    }
    
    public static int bfs(int l, int startX, int startY, int endX, int endY) {

        if (startX == endX && startY == endY){
        	return 0;
            }
        	
        boolean[][] visited = new boolean[l][l];
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(startX, startY, 0));
        visited[startX][startY] = true;
        
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            
            for (int i = 0; i < 8; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                if (nx >= 0 && nx < l && ny >= 0 && ny < l && !visited[nx][ny]) {
                    if (nx == endX && ny == endY) {
                        return current.count + 1;
                    }
                    queue.add(new Point(nx, ny, current.count + 1));
                    visited[nx][ny] = true;
                }
            }
        }
        
        return -1; 
    }
}

 

BFS 알고리즘을 사용해 체스판 위에서 나이트가 특정 위치에서 목표 위치로 가는 최소 거리를 구하는 문제 .

어떤 알고리즘을 사용해야 하는지는 확실하게 알았는데, 그것을 구현하는 과정에서 애를 먹어서 힌트를 찾아서 문제를 풀었다.