[백준/7562/Java] 나이트의 이동

나이트의 이동

 

 

문제

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

 

 

 

입력

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

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

 

 

출력

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

 

 

 

 

예제 입력 1

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

 

 

예제 출력 1

5
28
0

 

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.IntStream;

@BOJ(   number = 7562,
        tier = BaekjoonTier.SILVER_II,
        solveDate = @SolveDate(year = 2022, month = 2, day = 10))
public class 백준7562 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int TEST_SIZE = Integer.parseInt(br.readLine());
        for (int i =0; i< TEST_SIZE; i++){

            final int CHESS_SIZE = Integer.parseInt(br.readLine());
            Chess chess = Chess.from(CHESS_SIZE);
            int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int knigtX = s[0];
            int knigtY = s[1];

            s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int goalX = s[0];
            int goalY = s[1];

            int moveCountTo = chess.getMoveCountTo(knigtX, knigtY, goalX, goalY);
            System.out.println(moveCountTo);
        }

    }

    private static class Chess{
        private ArrayList<ArrayList<Integer>> map = new ArrayList<>();
        private ArrayList<ArrayList<Boolean>> visitedMap = new ArrayList<>();

        public Chess(final int SIZE) {
            IntStream.range(0,SIZE).forEach(i -> {
                ArrayList<Integer> temp = new ArrayList<>();
                ArrayList<Boolean> vTemp = new ArrayList<>();
                IntStream.range(0, SIZE).forEach(j -> {temp.add(0);vTemp.add(Boolean.FALSE);});
                map.add(temp);
                visitedMap.add(vTemp);
            });
        }

        public static Chess from(final int SIZE){
            return new Chess(SIZE);
        }

        public int getMoveCountTo(int x, int y, int goalX, int goalY){
            visitedMap.get(y).set(x, Boolean.TRUE);
            map.get(y).set(x,0);

            Deque<Position> deque = new ArrayDeque<>();
            deque.add(new Position(x,y));

            while (!deque.isEmpty()){
                Position current = deque.poll();
                int currentX = current.getX();
                int currentY = current.getY();

                if (currentX == goalX && currentY == goalY){
                    return map.get(currentY).get(currentX);
                }

                /**
                 * 움직일 수 있는 위치인지?
                 * 방문한 적이 없는지?
                 */
                List<Position> positions = current.movablePosition();
                positions.stream().filter(this::isMovable).filter(this::isNotVisited)
                        .forEach(position -> {
                            visitedMap.get(position.getY()).set(position.getX(), Boolean.TRUE);
                            map.get(position.getY()).set(position.getX(), map.get(currentY).get(currentX) + 1);
                            deque.offer(position);
                        });
            }
            return -1;
        }

        public boolean isMovable(Position position){
            int x = position.getX();
            int y = position.getY();
            return (x > -1 && y > -1) && (y < map.size() && x < map.size());
        }
        public boolean isNotVisited(Position position){
            return !visitedMap.get(position.getY()).get(position.getX());
        }
    }
    private static class Position {
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public List<Position> movablePosition() {
            List<Position> result = new ArrayList<>();
            result.add(new Position(x+2,y+1));
            result.add(new Position(x+2,y-1));
            result.add(new Position(x+1,y+2));
            result.add(new Position(x+1,y-2));
            result.add(new Position(x-2,y+1));
            result.add(new Position(x-2,y-1));
            result.add(new Position(x-1,y+2));
            result.add(new Position(x-1,y-2));
            return result;
        }
    }

}