BOJ_1331 : 나이트 투어

👉 문제링크

1331번: 나이트 투어

---

---

🔸 문제 분석 🔸

• 입력으로 주어진 루트가 체스의 나이트가 중복없이 움직이고, 마지막 까지 돌아올 수 있는지 확인한다.
  • 나이트는 8가지 방식으로 움직일 수 있다. (말 모양)
  • 중복된 곳을 밟으면 안된다.
  • 루트의 처음과 마지막도 나이트가 오갈 수 있어야 한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String input[] = new String[36];
        boolean arr[][] = new boolean[6][6];
        int night[][] = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};

        for (int i = 0; i < 36; i++)
            input[i] = sc.next();

        int x = 0, y = 0, new_x, new_y;

        new_x = 5 - (int)(input[0].charAt(1) - '1');
        new_y =  (int)(input[0].charAt(0) - 'A');
        x = new_x;
        y = new_y;
        arr[new_x][new_y] = true;

        for (int i = 1; i < 36; i++){
                new_x = 5 - (int)(input[i].charAt(1) - '1');
                new_y =  (int)(input[i].charAt(0) - 'A');

                int diff_x = new_x - x;
                int diff_y = new_y - y;

                boolean flag = false;
                for (int k = 0; k < 8; k++){
                    if (diff_x == night[k][0] && diff_y == night[k][1]){
                        if (!arr[new_x][new_y]){
                            arr[new_x][new_y] = true;
                            flag = true;
                            break;
                        }
                    }
                }

                if (!flag) {
                    System.out.println("Invalid");
                    System.exit(0);
                }

                x = new_x;
                y = new_y;
        }

        boolean flag = false;

        int diff_x = x - (5 - (int)(input[0].charAt(1) - '1'));
        int diff_y = y - (int)(input[0].charAt(0) - 'A');

        for (int k = 0; k < 8; k++){
            if (diff_x == night[k][0] && diff_y == night[k][1]){
                if (arr[new_x][new_y]){
                    arr[new_x][new_y] = true;
                    flag = true;
                    break;
                }
            }
        }

        if(flag)
            System.out.println("Valid");
        else
            System.out.println("Invalid");
    }
}

🔸 코드 해석 🔸

• 처음과 마지막을 따로 계산하기 위해서 1차원 배열에 입력을 저장했다.
  • 첫 위치는 해당 좌표만 기억한다.
• for 문을 돌며 좌표 이동대로 검사한다.
  • 중복된 좌표인지, 나이트가 움직일 수 있는 좌표인지 확인한다.
  • 만약 불가능하다면 Invalid를 출력하고 종료한다.
• 처음과 끝 좌표의 연결을 확인한다.

---

🔸 end 🔸

• 잠을 안자고 코테문제를 너무 많이풀었는지, 그렇게 어려운 문제는 아닌 것 같은데 엄청 오래걸렸다.
• 문제도 간단한 규칙 3가지였는데 파악을 늦게해서 코드를 계속 고쳐야했다.
• 마지막 제출도 형식을 맞추지 않는 등 집중력 하락이 많이 보였다. 코테는 잠을 푹 자야한다...