[백준 7562번] 나이트의 이동

문제 링크: 7562번 나이트의 이동

https://www.acmicpc.net/problem/문제번호

 

평범한 BFS 구현을 통해 최단거리를 구할 수 있다.

 

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

public class Main {
    static int[] drow = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dcol = {-2, -1, 1, 2, 2, 1, -1, -2};
    static class Pos {
        int row;
        int col;
        Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static void go(int n, int row1, int col1, int row2, int col2) {
        int[][] visit = new int[n][n];
        Queue<Pos> queue = new LinkedList<>();
        queue.offer(new Pos(row1, col1));
        visit[row1][col1] = 1;

        outer:
        while (!queue.isEmpty()) {
            Pos cur = queue.poll();
            int row = cur.row;
            int col = cur.col;

            for (int d = 0; d < 8; d++) {
                int nrow = row + drow[d];
                int ncol = col + dcol[d];

                if (nrow<0||ncol<0||nrow>=n||ncol>=n||visit[nrow][ncol]!=0)
                    continue;

                visit[nrow][ncol] = visit[row][col] + 1;
                queue.offer(new Pos(nrow, ncol));

                // 목표 지점 도착
                if (nrow==row2 && ncol==col2)
                    break outer;
            }
        }

        System.out.println(visit[row2][col2] - 1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        for (int t = 0; t < test; t++) {
            int n;
            int startRow;
            int startCol;
            int endRow;
            int endCol;
            int[] temp;

            n = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

            temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            startRow = temp[0];
            startCol = temp[1];
            temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            endRow = temp[0];
            endCol = temp[1];

            go(n, startRow, startCol, endRow, endCol);
        }
    }
}