[Python] 백준 1331번 - 나이트 투어

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

1331번: 나이트 투어

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 구현
 - 시뮬레이션

문제

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

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

입력

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

출력

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

 

---

 

이 문제는 총 3가지의 조건을 만족해야 "Valid" 결과가 나오는 문제이다.

 

1. 주어진 좌표에서 (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)의 8가지 방향에 맞게 움직이는가
2. 36개의 좌표가 중복되지 않는가
3. 마지막 좌표에서 처음좌표로 돌아갈 수 있는가

위의 세가지를 모두 충족하면 Valid

하나라도 만족하지 않는다면 Invalid를 출력하면 된다.

 

import sys
input = sys.stdin.readline

letters = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6}
data = [ [0] * 6 for _ in range(6)]
result = "Valid"

def dup(now):
    n1 = letters[now[0]]-1
    n2 = int(now[1])-1
    
    if data[n1][n2] == 0:
        data[n1][n2] = 1
    else:
        global result
        result = "Invalid"

def check(before, now):
    b1 = letters[before[0]]
    b2 = int(before[1])
    n1 = letters[now[0]]
    n2 = int(now[1])
    
    r1 = abs(b1 - n1)
    r2 = abs(b2 - n2)
    if ((r1 == 1 and r2 == 2) or (r1 == 2 and r2 == 1)):
        pass
    else:
        global result
        result = "Invalid"
        
before = input().rstrip()
falg = dup(before)
start = before
for _ in range(35):
    now = input().rstrip()
    
    check(before, now)
    dup(now)
    before = now
check(before, start)
    
print(result)

첫 번째 조건은 어쨌든 거리가 1, 2 혹은 2, 1만큼 움직였는가를 확인하면 되기 때문에

 

절댓값으로 계산하여 그 값을 비교한다.

 

두 번째 조건은 data 리스트를 통해서 중복된 좌표를 지나가는지 확인한다.

 

세 번째 조건은 첫 번째 좌표를 저장한 후 마지막 좌표를 다시 거리계산하여 확인한다.

 

그 후 결과값을 출력하면 끝.

 

처음엔 문제를 이해 못 하여 헷갈리고

 

마지막 좌표와 처음좌표를 비교해야 하는지 몰라서 생각보다 오래 걸렸다.