[BOJ/JAVA] 7562번: 나이트의 이동

7562번: 나이트의 이동

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

키워드

나이트가 한 번에 이동할 수 있는 칸은 아래와 같다.

이 때 원하는 위치에 가기까지 이동 횟수를 구하라

---

구현

final static int dydx[][]

현재 위치 기준으로 나이트가 이동할 수 있는 방향(8방향)을 기록한다.

private static int solution()

현재 위치에서 나이트가 목적지까지 갈 때 최소 이동 횟수를 반환한다.

• board[][]
  • 모든 위치의 값을 -1로 초기화한다.

• 현재 위치 기준으로 이동할 위치(toY, toX)를 계산한다.

• 해당 위치가 -1값이 아니라면(방문한 적이 없다면)
  • board[toY][toX] = here.count+1 로 갱신한다. (방문 처리)
  • 갈 수 있는 경로를 큐에 추가한다.

---

코드

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

public class java_7562 {
    // 나이트 이동 경우의 수
    final static int dydx[][] = { { -2, -1 }, { -1, -2 }, { 2, 1 }, { 1, 2 }, { -2, 1 }, { 2, -1 }, { -1, 2 },
            { 1, -2 } };

    // 테스트 케이스
    static int testCase;

    // 체스판 한 변의 길이
    static int l;

    static Pair startPoint, endPoint;

    static class Pair {
        int y, x;

        public Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + y;
            result = prime * result + x;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Pair other = (Pair) obj;
            if (y != other.y)
                return false;
            if (x != other.x)
                return false;
            return true;
        }

    }

    static class BoardPair {
        Pair pair;
        int count;

        public BoardPair(Pair pair, int count) {
            this.pair = pair;
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        testCase = Integer.parseInt(br.readLine());

        while (testCase-- > 0) {
            // 한 변의 길이
            l = Integer.parseInt(br.readLine());

            // 최초 위치
            StringTokenizer st = new StringTokenizer(br.readLine());
            startPoint = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            // 목표 위치
            st = new StringTokenizer(br.readLine());
            endPoint = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            int result = solution();

            System.out.println(result);
        }

        br.close();

    }

    private static int solution() {
        int result = 0;

        // 체스판
        int board[][] = new int[l][l];

        for (int i = 0; i < board.length; i++) {
            Arrays.fill(board[i], -1);
        }

        Queue<BoardPair> queue = new ArrayDeque<>();

        queue.add(new BoardPair(startPoint, 0));

        while (!queue.isEmpty()) {
            BoardPair here = queue.poll();

            if (here.pair.equals(endPoint)) {
                result = here.count;
                break;
            }

            // 갈 수 있는 방향
            for (int i = 0; i < dydx.length; i++) {
                try {
                    int toY = here.pair.y + dydx[i][0];
                    int toX = here.pair.x + dydx[i][1];

                    if (board[toY][toX] == -1) {
                        board[toY][toX] = here.count + 1;
                        queue.add(new BoardPair(new Pair(toY, toX), here.count + 1));
                    }
                } catch (ArrayIndexOutOfBoundsException e) {
                    continue;
                }
            }
        }

        return result;
    }
}

---

Uploaded by N2T