[JAVA] 백준 (실버1) 7562번 나이트의 이동

링크

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

---

문제 설명

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

---

입력 예제

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

---

출력 예제

5
28
0

---

정답 코드

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

public class Main {
	//나이트의 이동 방향
    static int[] dr = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[] dc = {1, 2, 2, 1, -1, -2, -2, -1};
    static int[][] chessBoard;
    static boolean[][] visit;
    static int length;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for (int testIndex = 0; testIndex < testCase; testIndex++) {

            length = Integer.parseInt(br.readLine());
            chessBoard = new int[length][length];   //체스판 배열
            visit = new boolean[length][length];    //방문 체크
            int[] start = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            int[] destination = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();

            bfs(start, destination);
			//목적지 원소 출력
            System.out.println(chessBoard[destination[0]][destination[1]]);
        }
    }
    
	//너비 완전 탐색 메서드
    static void bfs(int[] start, int[] destination) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visit[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            //큐의 첫번째 원소, 현재 좌표 할당
            int[] curPos = queue.poll();
            //목적지를 방문했을 경우 break
            if (visit[destination[0]][destination[1]]) {
                break;
            }
            //모든 방향 탐색
            for (int i = 0; i < dr.length; i++) {
                int nextR = curPos[0] + dr[i];
                int nextC = curPos[1] + dc[i];
                //범위를 벗어날 경우 continue
                if (nextR < 0 || nextC < 0 || nextR >= length || nextC >= length) {
                    continue;
                }
                //방문하지 않은 경우
                if (!visit[nextR][nextC]) {
                    //방문 처리
                    visit[nextR][nextC] = true;
                    //큐에 추가
                    queue.add(new int[]{nextR, nextC});
                    //좌표 갱신
                    chessBoard[nextR][nextC] = chessBoard[curPos[0]][curPos[1]] + 1;
                }

            }
        }
    }
}

---

정리

이전에 푼 미로 탐색 문제랑 비슷하였다. 일단 최소 이동 거리를 구해야 하므로 bfs를 이용한다.
그리고 탐색할 때마다 원소를 갱신하여 목적지를 도달할 때 까지 반복한다.