[Silver IV][JAVA] 백준 1331번:나이트 투어

백준 바로가기> [Silver IV]1331번:나이트 투어

※ 고려 사항

• 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며
• 나이트는 체스판에서 L자 모양으로 이동할 수 있으며, 이동 거리가 (2,1) 또는 (1,2)인 경우에만 이동이 가능합니다. (처음 위치와 마지막 위치 / 현재위치와 직전 위치 고려)

※ 풀이과정

L모양 체크 (dx, dy로 방향을 정하는 방법)

해당 함수는 이전 위치에서 가능한 모든 이동을 확인하여 다음 위치로 이동할 수 있는지 여부를 반환합니다.

prev: 현재 위치의 좌표를 나타내는 배열입니다.
next: 다음 위치의 좌표를 나타내는 배열입니다.

이 함수는 현재 위치 prev에서 이동할 수 있는 모든 경우를 확인합니다. 이동할 수 있는 경우는 나이트의 이동 규칙에 따라 L자 모양으로 이동하는 경우입니다. dx와 dy 배열은 나이트가 이동할 수 있는 8가지 방향을 나타내며, 이동하는 경우에 대한 x와 y 좌표의 변화를 저장하고 있습니다.

여기서 nx와 ny는 현재 위치에서 이동한 후의 좌표입니다. 이 좌표가 체스판을 벗어나지 않는지 확인합니다. 벗어난다면 해당 이동은 불가능하므로 건너뜁니다(continue).

그렇지 않은 경우에는 다음 위치인 next와 비교하여 현재 위치에서 다음 위치로 이동 가능한 경우가 있는지 확인합니다. 만약 가능한 경우가 있다면 true를 반환하고, 모든 경우에 대해 확인한 후에도 이동할 수 있는 경우가 없다면 false를 반환합니다.

    private static final int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
    private static final int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};

  private static boolean checkMove(int[] prev, int[] next) {
        for (int j = 0; j < 8; j++) {
            int nx = prev[0] + dx[j];
            int ny = prev[1] + dy[j];

            if (nx < 0 || nx >= 6 || ny < 0 || ny >= 6)
                continue;

            if (nx == next[0] && ny == next[1]) {
                return true;
            }
        }
        return false;
    }

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main { //유형: 구현, 메모리제한: 128MB, 시간 제한: 2초
    private static final int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
    private static final int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};

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

        boolean[][] visited = new boolean[6][6];
        int[] prev = new int[2];
        Arrays.fill(prev, -1);
        int firstx = 0;
        int firsty = 0;

        for (int i = 0; i < 36; i++) {
            String knightMove = br.readLine();
            int x = knightMove.charAt(0) - 'A';
            int y = knightMove.charAt(1) - '1';

            if (i == 0) {
                firstx = x;
                firsty = y;
            }

			// 현재위치와 직전 위치 고려
            if (prev[0] != -1 && !checkMove(prev, new int[]{x, y})) {
                System.out.println("Invalid");
                return;
            }

            if (visited[x][y]) { // 모든 칸 한 번씩
                System.out.println("Invalid");
                return;
            }

            visited[x][y] = true;

            prev[0] = x;
            prev[1] = y;

            if (i == 35) { // 처음 위치와 마지막 위치 이동 고려
                if (!checkMove(new int[]{firstx, firsty}, new int[]{prev[0], prev[1]})) { 
                    System.out.println("Invalid");
                    return;
                }
            }
        }

        System.out.println("Valid");
    }

    private static boolean checkMove(int[] prev, int[] next) {
        for (int j = 0; j < 8; j++) {
            int nx = prev[0] + dx[j];
            int ny = prev[1] + dy[j];

            if (nx < 0 || nx >= 6 || ny < 0 || ny >= 6)
                continue;

            if (nx == next[0] && ny == next[1]) {
                return true;
            }
        }
        return false;
    }
}