백준 7562번 나이트의 이동 (java)

[Silver I] 나이트의 이동 - 7562

문제 링크

성능 요약

메모리: 98092 KB, 시간: 484 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 4월 11일 11:32:43

문제 설명

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

입력

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

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

출력

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

 풀이

bfs와 dfs를 고민해봤는데, 모든 테스트 케이스에서 depth가 가장 작은 시도횟수를 찾기 위해선 bfs의 시간 복잡도가 더 낮을 것이라 생각해서

bfs로 풀이했다.

 

나이트의 모든 이동 경로는 다음과 같이 표현 가능하다.

 

X = {1,2,-1-2}

Y = {2,1,-2,-1}

 

newX = oldX + X[i]

newY = oldY + Y[i]

 

이후

newX = oldX + X[i]

newY = oldY + Y[i] * -1

 

을 돌아주면 나이트가 이동할 수 있는 모든 경우의 수가 나온다 이대로 bfs를 돌아주면 된다.

전체 코드

public class 나이트의이동 {

    static int len;
    static int endX;
    static int endY;
    static int max = 0;
    static int[] X = {1,2,-1,-2};
    static int[] Y = {-2,-1,2,1};
    static int flag = 0;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int i=0;i<T;i++){
            flag = 0;
            len = 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());

            endX = Integer.parseInt(st.nextToken());
            endY = Integer.parseInt(st.nextToken());
            visited = new boolean[len][len];

            Queue<int[]> queue = new LinkedList<>();
            visited[startX][startY] = true;
            queue.add(new int[]{startX,startY});
            bfs(0,queue);
            System.out.println(max);
            max = 0;
        }
    }

    public static void bfs(int depth, Queue<int[]> queue) {

        if(flag == 1){
            return;
        }

        Queue<int[]> newQueue = new LinkedList<>();

        while(!queue.isEmpty()){
            int[] now = queue.poll();

            if(now[0] == endX && now[1] == endY){
                max = depth;
                flag = 1;
                return;
            }

            for(int i=0;i<4;i++){
                int nowX = now[0]+X[i];
                int nowY = now[1]+Y[i];

                if(nowX >= 0 && nowX < len && nowY >= 0 && nowY < len){
                    if(!visited[nowX][nowY]) {
                        newQueue.add(new int[]{nowX, nowY});
                        visited[nowX][nowY] = true;
                    }
                }
            }

            for(int i=0;i<4;i++){
                int nowX = now[0]+X[i];
                int nowY = now[1]+Y[i]*-1;
                if(nowX >= 0 && nowX < len && nowY >= 0 && nowY < len){
                    if(!visited[nowX][nowY]) {
                        newQueue.add(new int[]{nowX, nowY});
                        visited[nowX][nowY] = true;
                    }
                }
            }
        }

        queue.addAll(newQueue);
        newQueue.clear();
        newQueue = null;
        bfs(depth+1,queue);
    }
}