[백준/JAVA] 🥈 7562번 나이트의 이동

문제

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

입력

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

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

출력

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

예제 입출력

 

 

 

풀이

 

https://rookie-programmer.tistory.com/92

예전에 풀었던 비슷한 문제인 송아지 찾기 BFS 풀었던 기억을 더듬어가며 풀이를 구체화했다.

 

(0, 0)에서 시작하는 나이트가 대충 저런 식으로 BFS 탐색하며 뻗어나간 후, Edge의 개수를 세어주면 될 것 같았다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -1};
    static int mapSize;
    static int[][] ch;
    static List<Integer> result = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(bf.readLine());
        int t = Integer.parseInt(st.nextToken());
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(bf.readLine()); //체스판 한 변의 길이 입력
            mapSize = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(bf.readLine()); //나이트가 현재 있는 칸
            int start_x = Integer.parseInt(st.nextToken());
            int start_y = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(bf.readLine()); //나이트가 이동하려는 칸
            int end_x = Integer.parseInt(st.nextToken());
            int end_y = Integer.parseInt(st.nextToken());

            BFS(start_x, start_y, end_x, end_y);
        }
        for(int x : result) System.out.println(x);
    }
    public static void BFS(int s_x, int s_y, int e_x, int e_y){
        ch = new int[mapSize][mapSize];
        ch[s_x][s_y]=1;
        Queue<Point> Q = new LinkedList<>();
        Q.add(new Point(s_x, s_y));
        //뻗어나간 Depth 깊이로 최단경로 찾기 = 정답
        int level=0;
        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                Point cur = Q.poll();
                if(cur.x == e_x && cur.y == e_y) {
                    result.add(level);
                    return;
                }
                for (int j = 0; j < 8; j++) {
                    int nx = cur.x + dx[j];
                    int ny = cur.y + dy[j];
                    if(nx>=0 && nx<mapSize && ny>=0 && ny<mapSize && ch[nx][ny]==0) {
                        ch[nx][ny]=1;
                        Q.add(new Point(nx, ny));
                    }
                }
            }
            level++;
        }
    }
}

 

 

버뜨, 첫 번째 테케에서 무슨 잘못이 일어나는 게 틀림없다....

내 완벽한 논리에서 탈출하는 방법 좀 알려주엉....

화요일까지 문제 해결 간다. 딱대 나이트.

 

 

 

는 멋쟁이 팀원들이 찾아줬다..........................

반성해 나자신............. 눈 똑바로 떠.......... 세상은 호락호락하지 않아................ (이 멍청아)

 

 

 

dy배열만 고치니까 잘된다....ㅎ_ㅎ