[BOJ_7562] 나이트의 이동 (Java)

728x90

문제링크

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

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

www.acmicpc.net

문제설명

문제

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

입력

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

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

출력

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

제한사항

제한시간	메모리제한
1초	256 MB

출처 : https://www.acmicpc.net

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
BFS

나이트의 이동 문제는 BFS를 활용하여 해결 할 수 있습니다. 체스판을 모두 하나의 정점으로 보고, 나이트가 이동할 수 있는 길을 간선으로 연결된 정점들 생각하며 문제를 해결하면 됩니다. 최단거리에 대한 문제이기 때문에 DFS를 사용할 수 없습니다. BFS를 시작 정점부터 돌려주면 이동가능한 모든 보드판의 위치에 최단거리를 기록할 수 있습니다.

이 때 bfs를 돌며 체크된 정점인지 확인을 하기 위하여 정수로 해당 위치의 최단거리를 표시해주면 됩니다.

구현코드

package backjoon_7562;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();

        while ((testCase--) != 0){
            int chessLen = sc.nextInt();
            int[][] board = new int[chessLen][chessLen];
            for(int i = 0; i < chessLen; i++){
                for(int j = 0; j < chessLen; j++){
                    board[i][j] = -1;
                }
            }
            int startX = sc.nextInt();
            int startY = sc.nextInt();
            int finishX = sc.nextInt();
            int finishY = sc.nextInt();

            Queue<Integer> queue = new LinkedList<>();
            queue.add(startX);
            queue.add(startY);
            board[startX][startY] = 0;

            while (!queue.isEmpty()){
                bfs(queue,board);
            }
            System.out.println(board[finishX][finishY]);
        }
    }

    public static void bfs(Queue<Integer> queue, int[][] board){
        int X = queue.remove();
        int Y = queue.remove();
        int[] dX = {-2,-1,1,2,2,1,-1,-2};
        int[] dY = {1,2,2,1,-1,-2,-2,-1};

        for(int i = 0; i < 8; i++){
            if(X + dX[i] >= 0 && X + dX[i] < board.length &&
                    Y + dY[i] >= 0 && Y + dY[i] < board.length){
                if(board[X+dX[i]][Y+dY[i]] == -1) {
                    queue.add(X + dX[i]);
                    queue.add(Y + dY[i]);
                    board[X + dX[i]][Y + dY[i]] = board[X][Y] + 1;
                }
            }
        }
    }
}

시간복잡도

테스트 케이스의 수만큼 확인하기 때문에 T를 곱해주어야합니다.

모든 정점에 대하여 한번씩은 수행하기 때문에 V이고 해당 정점과 연결된 8개의 간선을 확인해주기 때문에 E가 됩니다.

따라서 시간 복잡도는 $O(T*(V+E))$가 됩니다.