백준 - 나이트의 이동

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/7562

 

[문제 설명]

체스판의 시작 좌표와 도착 좌표가 주어졌을 때, 도착 좌표까지 몇번만의 이동할 수 있나?

[접근 방법]

BFS로 풀었다.

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

public class Main {
    static boolean[][] visited;
    static int[][] moveDirection = new int[][]{
            {-2,1},
            {-1,2},
            {1,2},
            {2,1},
            {2,-1},
            {1,-2},
            {-1,-2},
            {-2,-1}
    };

    public static void main(String[] args) throws IOException {
        // 행,컬럼순 (위로 가면 -, 아래로 가면 +, 왼쪽으로 가면 -오른쪽으로 가면 +. 1시방향부터 시작.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numOfTestcases = Integer.parseInt(br.readLine());
        while (numOfTestcases-- > 0) {
            int lengthOfBoard = Integer.parseInt(br.readLine());
            visited = new boolean[lengthOfBoard][lengthOfBoard];
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int[] startPoint = new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
            st = new StringTokenizer(br.readLine()," ");
            int[] targetPoint = new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};

            System.out.println(getMoveCnt(lengthOfBoard, startPoint, targetPoint));
        }
    }

    private static int getMoveCnt(int lengthOfBoard, int[] startPoint, int[] targetPoint) {
        if (startPoint[0]==targetPoint[0] && startPoint[1]==targetPoint[1]) {
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(startPoint);
        int moveNum = 0;

        while (!queue.isEmpty()) {
            int qSize = queue.size();
            for (int i = 1; i <= qSize; i++) {
                int[] currentPosition = queue.poll();
                if (visited[currentPosition[0]][currentPosition[1]]) {
                    continue;
                }
                visited[currentPosition[0]][currentPosition[1]] = true;

                for (int[] move : moveDirection) {
                    int nextYposition = currentPosition[0]+move[0];
                    int nextXposition = currentPosition[1]+move[1];
                    if (nextXposition < 0 || nextXposition >= lengthOfBoard || nextYposition < 0 || nextYposition >= lengthOfBoard) {
                        continue;
                    }
                    if (nextYposition==targetPoint[0] && nextXposition==targetPoint[1]) {
                        return ++moveNum;
                    }

                    queue.offer(new int[]{nextYposition,nextXposition});
                }
            }
            moveNum++;
        }

        return -1;
    }
}

시간복잡도는 모든 정점을 방문하고 모든 간선을 확인해야하니

간선의 개수 8, 모든 정점의 개수 N^2해서 최악의 경우 O(8N^2)이다.

따라서 최대 연산 횟수는 가로의 길이*세로의 길이*간선의 개수인 300*300*8 = 720,000이다.