백준 1331번: 나이트 투어

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

 

6*6 체스판에서 시작점부터 모든 위치를 방문하면서 마지막 위치에 도착하여 시작점으로 돌아올 수 있는지 판단하는 문제이다.

 

시작점을 저장하고, 재방문 하지 않게 확인하면서 마지막점 도착 후 시작점에 돌아올 수 있는지 확인하여 가능하면 Valid, 불가능하면 Invalid를 출력한다. 나이트가 방문 가능한 경우는 가본적 없으면서 이전 위치와 가로 1~2칸 차이, 세로 1~2칸 차이 이고 가로 차이 + 세로 차이 합이 3이여야 한다. 또한, 가로는 A~F, 세로는 1~6으로 주어진다.

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

public class 나이트투어1331 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[][] visited = new boolean[6][6];
        String first = br.readLine();
        int prevX = first.charAt(0) - 'A', prevY = first.charAt(1) - '1';
        int firstX = prevX, firstY = prevY;
        visited[prevX][prevY] = true;
        for (int i = 0; i < 35; i++) {
            String pos = br.readLine();
            int x = pos.charAt(0) - 'A', y = pos.charAt(1) - '1';
            if (prevX == x || y == prevY) {
                System.out.print("Invalid");
                br.close();
                return;
            }
            if (Math.abs(prevX - x) + Math.abs(prevY - y) != 3) {
                System.out.print("Invalid");
                br.close();
                return;
            }
            if (visited[x][y]) {
                System.out.print("Invalid");
                br.close();
                return;
            }
            visited[x][y] = true;
            prevX = x;
            prevY = y;
        }
        if (Math.abs(prevX - firstX) + Math.abs(prevY - firstY) != 3) {
            System.out.print("Invalid");
        } else {
            System.out.print("Valid");
        }
        br.close();
    }
}