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

package boj;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class KnightNode {
    int[] coordinate;
    int[][] visitedNodes;
    int depth = 0;
    
    //최초의 나이트 노드 생성용
    
    public KnightNode(int[] coordinate, int boardLength) {
        this.coordinate = coordinate;
        this.visitedNodes = new int[boardLength][boardLength];
        this.visit(coordinate);
    }
    
    // bfs를 돌며 생성되는 나이트 노드 생성용 생성자
    public KnightNode(int[] coordinate, int[][] visitedNodes, int depth) {
        this.coordinate = coordinate;
        
        //new int[][] visitedNodes를 하지 않고 visitedNodes를 그대로 가리키게 하면
        //각각의 나이트 노드가 같은 visitedNodes를 가리키게 되어서
        //나이트 노드 각각의 visitedNodes가 생성되는 것이 아니라
        //전역의 visitedNodes를 가리키게 된다.
        
        this.visitedNodes = visitedNodes;
        this.depth = depth;
    }

    public void visit(int[] coordinate) {
    // 방문한 노드를 표시한다.
        this.visitedNodes[coordinate[0]][coordinate[1]] = 1;
    }
    public boolean checkVisited(int[] coordinate) {
        // 방문했으면 참, 방문하지 않았으면 거짓
        if (this.visitedNodes[coordinate[0]][coordinate[1]] == 1) {
            return true;
        }
        else {
            return false;
        }
    }
}
public class newboj7562 {
    static int testCaseNumber;
    static ArrayList<ArrayList<int[]>> testCases = new ArrayList<>();
    static ArrayList<int[]> movementMetrix = new ArrayList<>();
    static int[][] visitedList;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        inputMethod(scanner);
        
        //나이트가 이동할 수 있는 방향을 저장한다.
        
        movementMetrix.add(new int[] {-2, -1});
        movementMetrix.add(new int[] {-2, 1});
        movementMetrix.add(new int[] {-1, -2});
        movementMetrix.add(new int[] {1, -2});
        movementMetrix.add(new int[] {-1, 2});
        movementMetrix.add(new int[] {+1, 2});
        movementMetrix.add(new int[] {2, -1});
        movementMetrix.add(new int[] {2, 1});

        for(ArrayList<int[]> testCase : testCases) {
            KnightNode answerKnight = bfs(testCase);
            System.out.println(answerKnight.depth);

        }
    }
    public static KnightNode bfs(ArrayList<int[]> testCase) {
        int[] boardLength = testCase.get(0);
        int[] nowPosition = testCase.get(1);
        int[] destination = testCase.get(2);

        visitedList = new int[boardLength[0]][boardLength[0]];

        ArrayDeque<KnightNode> model = new ArrayDeque<>();
        model.addLast(new KnightNode2(nowPosition, boardLength[0]));

        while (model.size() != 0) {
            KnightNode selectedKnight = model.pollFirst();
            if (Arrays.equals(selectedKnight.coordinate, destination)) {
                return selectedKnight;
            }
            else {
                ArrayList<int[]> coordinates = getKnightMoves(boardLength[0],
                        selectedKnight.coordinate);

                for (int[] x : coordinates) {
                    if(selectedKnight.checkVisited(x)) {// 방문했으면 pass
                    }
                    else {
                        KnightNode tempKnight = new KnightNode2(x, 
                         selectedKnight.visitedNodes, selectedKnight.depth + 1);
                        tempKnight.visit(x);
                        model.addLast(tempKnight);
                    }
                }
            }
        }
        return null;
    }
    public static ArrayList<int[]> getKnightMoves(int boardLength, int[] coordinates) {
        ArrayList<int[]> returnArray = new ArrayList<>();
        for(int[] x : movementMetrix) {
            int[] tempCoordinates = new int[2];
            int i = 0;
            for(int y : x) {
                tempCoordinates[i] = coordinates[i++] + y;
            }
            if(checkBoardLimit(boardLength, tempCoordinates)) {
                // BoardLimit내에 위치하면
                returnArray.add(tempCoordinates);
            }
        }
        return returnArray;
    }
    public static boolean checkBoardLimit(int boardLength, int[] coordinate) {
        for (int x : coordinate) {
            if (x < 0) {
                return false;
            }
            else if (x >= boardLength) {
                return false;
            }
        }
        return true;
    }
    public static void inputMethod(Scanner scanner) {
        newboj7562.testCaseNumber = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < newboj7562.testCaseNumber; i++) {
            ArrayList<int[]> testCase = new ArrayList<>();
            int boardLength = scanner.nextInt();
            testCase.add(new int[] {boardLength});
            scanner.nextLine();

            for (int j = 0; j < 2; j++) {
                String coordinates = scanner.nextLine();
                int[] parsedLine = parsingString(coordinates);
                testCase.add(parsedLine);
            }
            testCases.add(testCase);
        }
    }
    public static int[] parsingString(String string) {
        String[] tempString = string.split(" ");
        int[] ints = new int[2];

        int i = 0;
        for (String x : tempString) {
            int temp = Integer.parseInt(x);
            ints[i++] = temp;
        }
        return ints;
    }
}