[백준] 1331번: 나이트 투어 - 파이썬

🔈 문제

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

 

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

 

 

📝입력

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

 

📑출력

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

 

📚 문제 해석

나이트의 이동은 (1,2),(1,-2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1) 가 가능하다.
Invalid 판정을 받는 경우는 3가지 정도 있다.

첫번째 : 나이트의 이동에 따르지 않는 경우. 예를 들어 (3,0) 이렇게 이동
두번째 : 방문했던 곳을 다시 방문하는 경우. 36번만에 모든 체스판을 방문하려면 같은곳 다시 방문하면 안된다.
세번째 : 마지막까지 이동을 마친 자리에서 한번 움직여서 다시 처음 위치로 도달할 수 없을 때.

입력받은 값들을 위 사항들로 체크하여 답을 유추해내었다.

 

 

나이트의 이동에 따르는 경우

if (abs(ord(pre[0]) - ord(now[0])) ==1 and abs(int(pre[1])-int(now[1])) == 2):
	pass
elif (abs(ord(pre[0]) - ord(now[0])) ==2 and abs(int(pre[1])-int(now[1])) == 1):
    pass

 

방문했던 곳을 다시 방문하지 않는 경우

if now not in visited:
	pass

 

💻 코드

import sys
input = sys.stdin.readline
ans = "Valid"
visited = [] # 방문했던 곳을 담을 리스트
for i in range(36):
    if i == 0: # 마지막값과 체크하기 위하여 따로 빼놓음
        start = input().rstrip()
        pre = start
    elif i < 35:
        now = input().rstrip()
        if ((abs(ord(pre[0]) - ord(now[0])) ==1 and abs(int(pre[1])-int(now[1])) == 2) or (abs(ord(pre[0]) - ord(now[0])) ==2 and abs(int(pre[1])-int(now[1])) == 1)) and now not in visited:
            pass
        else:   
            ans = "Invalid"
        visited.append(now) # 방문리스트에 삽입
        pre = now
    else:
        now = input().rstrip()
        if ((abs(ord(now[0]) - ord(start[0])) ==1 and abs(int(now[1])-int(start[1])) == 2) or (abs(ord(now[0]) - ord(start[0])) ==2 and abs(int(now[1])-int(start[1])) == 1)) and now not in visited:
            pass
        else:
            ans = "Invalid"

print(ans)