[백준] 문제 7562번 : 나이트의 이동

[링크] : https://www.acmicpc.net/problem/7562

---

💎 문제 분석 & 제약 조건

 

 

문제 분석 :

 

 

체스판 위에 한 나이트가 놓여져 있는데, 나이트가 이동하려고 하는 칸이 주어진다.

  
나이트는 몇 번 움직이면 이 칸으로 이동할 수 있는지 구한다.

 

 

제약 조건 : 

 

 

체스판의 한 변의 길이 l(4 ≤ l ≤ 300)

체스판의 크기는 l × l 

체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다.

 

---

🚀 의사 결정

 

 

1. BufferedReader로 테스트 케이스의 개수를 입력 받는다

 

2. 나이트의 이동 방향을 정의하고 , 체스판의 한 변의 길이를 입력 받는다.

 

3. StringTokenizer를 이용하여 , 나이트의 시작 위치를 토큰화 하고 startX , startY에 할당한다.

 

4. StringTokenizer를 이용하여 ,나이트의 목표 위치를 토큰화 하고 endX , endY에 할당한다.

 

5. 방문 여부를 체크하는 배열을 visited에 할당하고 , BFS(너비우선탐색)을 위한 큐를 만들어서, 시작위치 startX 와 startY  그리고 초기 이동 횟수 (0)을 큐에 넣어준다.

 

6. 시작위치는 방문 처리하여 , boolean 값을 true 로 설정한다.

 

7. while 조건 문에서 큐가 빈값이 아닌 조건을 설정하고 큐에서 현재 위치와 이동 횟수를 큐에서 꺼내서 목표 위치에 도달하면 이동 횟수를 출력하고,

 

8. 나이트의 8가지 이동 방향을 반복문을 이용해서 탐색한다. 

 

9. 이 때, 유효한 범위 내에 있고 방문하지 않은 경우 조건문으로 if문을 사용해서 방문처리 하고, 다음 위치와 이동 횟수를 추가한다.

 

10. 최종적으로 최소 몇번 만에 이동할 수 있는지 결과를 출력한다.

 

---

📜 소스코드(Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCaseCount = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수 입력

        // 나이트의 8가지 이동 방향 정의
        // 두 칸 수평으로 이동한 후 한 칸 수직으로 이동
        // 두 칸 수직으로 이동한 후 한 칸 수평으로 이동
        int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
        // dx는 이동할 수 있는 x축(수평 방향)의 변화

        int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
        // dy는 이동할 수 있는 y축(수직 방향)의 변화
        /*
        (-2, 1): 두 칸 왼쪽, 한 칸 위
        (-1, 2): 한 칸 왼쪽, 두 칸 위
        ( 1, 2): 한 칸 오른쪽, 두 칸 위
        ( 2, 1): 두 칸 오른쪽, 한 칸 위
        ( 2, -1): 두 칸 오른쪽, 한 칸 아래
        ( 1, -2): 한 칸 오른쪽, 두 칸 아래
        (-1, -2): 한 칸 왼쪽, 두 칸 아래
        (-2, -1): 두 칸 왼쪽, 한 칸 아래
         */
        StringBuilder sb = new StringBuilder();

        for (int t = 0; t < testCaseCount; 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());

            boolean[][] visited = new boolean[l][l]; // 방문 여부를 체크하는 배열
            Queue<int[]> queue = new LinkedList<>(); // BFS를 위한 큐
            queue.add(new int[]{startX, startY, 0}); // 시작 위치와 초기 이동 횟수(0) 추가
            visited[startX][startY] = true; // 시작 위치 방문 처리

            while (!queue.isEmpty()) {
                int[] current = queue.poll(); // 현재 위치와 이동 횟수를 큐에서 꺼냄
                int x = current[0];
                int y = current[1];
                int moves = current[2];

                // 목표 위치에 도달하면 이동 횟수 출력
                if (x == endX && y == endY) {
                    sb.append(moves).append("\n");
                    break;
                }

                // 나이트의 8가지 이동 방향을 탐색
                for (int i = 0; i < 8; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    // 유효한 범위 내에 있고 방문하지 않은 경우
                    if (nx >= 0 && nx < l && ny >= 0 && ny < l && !visited[nx][ny]) {
                        visited[nx][ny] = true; // 방문 처리
                        queue.add(new int[]{nx, ny, moves + 1}); // 다음 위치와 이동 횟수 추가
                    }
                }
            }
        }
        System.out.print(sb.toString()); // 결과 출력
    }
}