BOJ 1331 - 나이트 투어 (Python)

S4, 구현

문제 설명

나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다.

영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.

입력

36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

입력예시

A1
B3
A5
C6
E5
F3
D2
F1
E3
F5
D4
B5
A3
B1
C3
A2
C1
E2
F4
E6
C5
A6
B4
D5
F6
E4
D6
C4
B6
A4
B2
D1
F2
D3
E1
C2

출력예시

Valid

풀이

Invalid가 되는 3가지 조건을 찾는다

1. 이미 방문한 곳을 다시 방문했을 때
2. 나이트의 이동이 아닌 다른 이동방법일 때,
   -> ex) [1,3] -> [5,5]
3. 마지막 지점에서 첫번째 지점으로 이동할 수 없을 때

# 나이트 투어, S4

x_wi = {'A' : 1, 'B' : 2, 'C' : 3, 'D' : 4, 'E' : 5, 'F' : 6}
arr = []
for i in range(36):
    arr.append(input().rstrip())

visited = []
prev = [x_wi[arr[0][0]], int(arr[0][1])]
visited.append(prev)
for move in arr[1:]:
    x, y = move[0], int(move[1])
    cx = x_wi[x]
    if [cx, y] in visited:
        print("Invalid")
        exit()

    if abs(prev[0] - cx) == 1 and abs(prev[1] - y) == 2:
        prev = [cx, y]
        visited.append(prev)
        continue
    elif abs(prev[0] - cx) == 2 and abs(prev[1] - y) == 1:
        prev = [cx, y]
        visited.append(prev)
        continue
    else:
        print("Invalid")
        exit()

if abs(visited[-1][0] - visited[0][0]) + abs(visited[-1][1] - visited[0][1]) != 3:
    print("Invalid")
    exit()

print("Valid")