[알고리즘/백준] 1331번 나이트 투어 Python 파이썬

 

이번 문제는 체스의 룰을 알고 확인할 조건들과 규칙을 찾아낼 수 있으면 풀 수 있는 문제이다.

 

 

주의있게 봐야할 점이

1. 나이트의 움직임 규칙

2. 모든 지점을 한번씩만 들렸는지

3. 마지막 지점에서 처음 지점으로 갈 수 있는지

총 3가지 조건이다. 

 

1. 경우 나이트 움직임이 x, y 좌표 값으로 변환했을 때 현재 움직임 nowx, nowy 다음 움직임 prex, prey 라 할 때 abs(nowx-prex) == 1 and abs(nowy-prey) == 2)  이거나 (abs(nowx-prex) == 2 and abs(nowy-prey) == 1 조건에 충족하는지 확인해야한다. 만약이 이 경우를 제외하고는 나이트 이동 규칙을 지키지 않은 것이다.

 

2. chass_map 이라는 이차원 배열 만들어서 지나갈때마다 +1 해서 검사해주었다. 만약에 0 이거나 2 이상이면 안 지나가거나 여러번 지나갔기 때문에 Invalid 가 된다.

 

3. 마지막, 처음 지점을 저장하고 1번처럼 검사해주었다.

 

다음과 같은 코드를 통해 통과하였다.

 

import sys
input = sys.stdin.readline

chass_map = [ [0] * 6 for _ in range(6) ] # 한번만 지나갔는지 체크하는 지도
prex, prey = 0, 0
nowx, nowy = 0, 0
num = 0 

for i in range(36):
    pos = input()
    nx, ny = 0, 0 # 현재 입력받은 x, y 점
    if pos[0] == 'A':
        chass_map[0][int(pos[1])-1] += 1 # 지도에 +1
        nx, ny = 0, int(pos[1])-1
    elif pos[0] == 'B':
        chass_map[1][int(pos[1])-1] += 1
        nx, ny = 1, int(pos[1])-1
    elif pos[0] == 'C':
        chass_map[2][int(pos[1])-1] += 1
        nx, ny = 2, int(pos[1])-1
    elif pos[0] == 'D':
        chass_map[3][int(pos[1])-1] += 1
        nx, ny = 3, int(pos[1])-1
    elif pos[0] == 'E':
        chass_map[4][int(pos[1])-1] += 1
        nx, ny = 4, int(pos[1])-1
    elif pos[0] == 'F':
        chass_map[5][int(pos[1])-1] += 1
        nx, ny = 5, int(pos[1])-1
    if i == 0:
        sx, sy = nx, ny # 처음 지점
    if i == 35:
        fx, fy = nx, ny # 마지막 지점
    if i%2 == 0:
        nowx, nowy = nx, ny
    if i%2 == 1:
        prex, prey = nx, ny
    if i != 0: # 처음에는 비교할 대상이 없으니 예외 처리 / 아래는 나이트 이동에 충족하는지 체크
        if (abs(nowx-prex) == 1 and abs(nowy-prey) == 2) or (abs(nowx-prex) == 2 and abs(nowy-prey) == 1):
            pass
        else:
            num = 1
            break


for i in range(6): # 지도 체크 
    for j in range(6):
        if chass_map[i][j] != 1: # 만약 1이 아닐 시 안 지나갔거나 여러번 지나갔거나
            num = 1
            
if num == 1:
    print("Invalid")
else: # 마지막 지점 -> 처음 지점으로 가능한지 체크
    if (abs(sx-fx) == 1 and abs(sy-fy) == 2) or (abs(sx-fx) == 2 and abs(sy-fy) == 1):
        print("Valid")
    else:
        print("Invalid")

 

코드가 길고 복잡해 더 줄이고 싶었으나 시간 여건상 그대로 제출했다.