백준 1331번 파이썬 풀이 : 나이트 투어

문제 링크 : https://www.acmicpc.net/problem/1331

1331번: 나이트 투어

문제

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

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

입력

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

출력

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

 

# 문제 풀이

[예제 입력란은 36개로 너무 길어 생략]

 

chess = [[0, 0, 0, 0, 0, 0] for _ in range(6)]

 

먼저 방문한 칸을 구별하기 위해 체스 판을 생성한다.

 

 

alpha = {'A': 0, "B": 1, "C": 2, "D": 3, "E": 4, "F": 5}
answer = True
temp_x, temp_y = 0, 0
first_x, first_y = 0, 0

 

temp 변수는 나이트가 이전에 방문한 위치를 저장하기위한 변수이며

first 변수는 나이트가 맨 마지막 칸을 방문 후 첫번째 칸으로 와야하기 때문에 그 첫번째 칸을 저장한 변수이다.

 

 

for i in range(36):
    knight = input()
    if i == 0:
        temp_x = alpha[knight[0]]
        temp_y = int(knight[1]) - 1
        first_x = alpha[knight[0]]
        first_y = int(knight[1]) - 1
        chess[temp_x][temp_y] = 1

 

입력값은 무조건 36개이기 때문에 반복문을 36번 반복해준다.

첫번째 반복은 이전의 움직임이없기 때문에 temp와 first에 각각 저장해주고 첫 칸을 1로 표시해준다.

 

 

    else:
        now_x = alpha[knight[0]]
        now_y = int(knight[1]) - 1
 
        # 나이트가 갈 수 있는 곳인지 체크
        if not check_knight(temp_x, temp_y, now_x, now_y):
            answer = False
 
        # 이미 해당하는 곳이 한번 들렸던 경우
        if chess[now_x][now_y] == 1:
            answer = False
 
        if i == 35:
            if not check_knight(first_x, first_y, now_x, now_y):
                answer = False
 
        chess[now_x][now_y] = 1
        temp_x = now_x
        temp_y = now_y

 

now 변수에 현재 말이 가야하는 곳의 좌표를 저장하고 check_knight 함수를 통해 해당 좌표가 나이트가 움직일 수 있는 곳인지 확인한다.

 

만일 움직일 수 없는 곳이면 bool 형 변수 answer를 false 로 바꿔준다.

 

여기서 false로 바꾸는 동시에 break를 걸어주지 않는 이유는 36개 모두 입력을 받아야 하기 때문이다.

 

또한 이동해야하는 좌표의 값이 1일 경우 이미 한번 거쳐간 위치이기 때문에 동일하게 answer를 false로 바꿔준다.

 

i가 35일때는 나이트가 마지막 칸을 방문한 상태이기 때문에 첫 번째 좌표와 check_knight 함수를 통해 이동할 수 있는 위치인지 파악하며 뒤와 동일하게 answer 변수를 설정해준다.

 

위의 예외가 아닌 이동할 수 있는 경우 해당 좌표의 값을 1로 변경

 

temp의 변수를 현재 이동한 좌표로 변경하여 다음 말이 사용할 수 있도록 바꿔 준다.

 

 

if answer:
    print("Valid")
else:
    print("Invalid")

 

answer가 True일 경우 나이트가 모든 좌표를 이동한 것이기 때문에 Valid를 출력하고 False일 경우 Invalid를 출력한다.

 

[Check_knight 함수]

def check_knight(t_x, t_y, n_x, n_y):
    if (abs(t_x - n_x) ** 2) + (abs(t_y - n_y) ** 2) == 5:
        return True
    else:
        return False

 

나이트가 이동할 수 있는 모든 위치를 현재 있는 위치와 계산하게 된다면 5가 나오게 된다.

따라서 입력받은 2개의 좌표의 거리가 5이게되면 True를 아니면 False를 리턴한다.

 

 

# 전체 코드

def check_knight(t_x, t_y, n_x, n_y):
    if (abs(t_x - n_x) ** 2) + (abs(t_y - n_y) ** 2) == 5:
        return True
    else:
        return False
 
 
chess = [[0, 0, 0, 0, 0, 0] for _ in range(6)]
alpha = {'A': 0, "B": 1, "C": 2, "D": 3, "E": 4, "F": 5}
answer = True
temp_x, temp_y = 0, 0
first_x, first_y = 0, 0
 
for i in range(36):
    knight = input()
    if i == 0:
        temp_x = alpha[knight[0]]
        temp_y = int(knight[1]) - 1
        first_x = alpha[knight[0]]
        first_y = int(knight[1]) - 1
        chess[temp_x][temp_y] = 1
 
    else:
        now_x = alpha[knight[0]]
        now_y = int(knight[1]) - 1
 
        # 나이트가 갈 수 있는 곳인지 체크
        if not check_knight(temp_x, temp_y, now_x, now_y):
            answer = False
 
        # 이미 해당하는 곳이 한번 들렸던 경우
        if chess[now_x][now_y] == 1:
            answer = False
 
        if i == 35:
            if not check_knight(first_x, first_y, now_x, now_y):
                answer = False
 
        chess[now_x][now_y] = 1
        temp_x = now_x
        temp_y = now_y
 
if answer:
    print("Valid")
else:
    print("Invalid")