나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다.
영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.
36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
구현 문제 중에서도 간단하지만, 핵심을 담고 있다고 생각한다. 개인적으로 알고리즘 문제풀이에 있어서 처음 풀어봐야 할 문제 중 하나가 되겠다 싶다.
우선, 다음과 같은 조건으로 정리할 수 있다.
1. 나이트의 이동 규칙이 지켜져야 한다. 나이트의 좌표 이동은 무조건 (x 또는 y가 1칸), (나머지 축이 2칸)을 움직이게 되는 구조이다.
2. 나이트의 이동 시 한 번이라도 이동했던 칸으로 이동해서는 안 된다. 따라서 방문 여부를 체크해주어야 한다.
3. 나이트의 이동 완료 시 모든 칸을 방문했어야 한다. 사실 2번과 같이 체크할 수 있으나 풀이에 반영하지는 않았었다.
4. 나이트의마지막 좌표와 나이트의 첫 번째 좌표 역시 이동 규칙을 지켜야 한다. 그래야 마지막 칸에서 시작점으로 돌아올 수 있으니까.
이 점을 염두해 두고 풀이하면 끝!
풀이 코드
def coord_check(x):
return (ord(x[0])-ord('A'), int(x[1])-1)
def is_valid(sx, sy, ex, ey):
return abs(sx - ex) == 1 and abs(sy - ey) == 2 or abs(sx - ex) == 2 and abs(sy - ey) == 1
visited = [[1]*6 for _ in range(6)]
vaild = True
for i in range(36) :
x, y = coord_check(input())
if (i > 0 and not is_valid(x, y, prev_x, prev_y)) or visited[y][x] == 0:
vaild = False
break
if i == 0 :
sx, sy = x, y
visited[y][x] = 0
prev_x, prev_y = x, y
print('Valid' if vaild and sum(map(sum, visited)) == 0 and is_valid(sx, sy, x, y) else 'Invalid')
