[python/파이썬] 백준 1331 나이트 투어

[문제 출처]

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

1331번: 나이트 투어

 

[문제 풀이]

 

입력으로 주어진 경로가 나이트 투어인지 아닌지 출력하는 문제이다.

 

나이트 투어란 3가지 조건을 만족한다.

1) 나이트가 정상적으로 이동했는가?

> 나이트는 상하좌우 중 한 칸, 대각선 중 한 칸 움직일 수 있다. 

칸의 번호로 따지면, 가로로 1칸 세로로 2칸 차이 나거나, 가로로 2칸 세로로 1칸 차이나는 경우이다.

 

2) 나이트가 모든 칸에 방문했는가?

> 나이트가 모든 칸에 방문하여 마지막 칸에서 다시 시작점으로 돌아와야 하므로 방문하지 않는 칸은 없어야 한다.

 

3) 마지막 칸에서 출발점으로 돌아올 수 있는가?

> 마지막 칸에서 출발점으로 나이트의 움직임으로 돌아올 수 있는지 확인해야 한다.

 

 

체스판 칸의 번호는 행은 숫자로, 열을 알파벳으로 나타나있다.

따라서 칸의 번호를 입력받고, 숫자의 경우 일반적인 정수의 연산을 하고, 알파벳을 아스키코드로 변환하여 연산한다.

 

1) 현재 있는 칸과, 움직일 칸의 행과 열의 번호의 차이가 (2,1) 이거나 (1,2) 인지 확인한다.

2) 칸의 리스트를 집합으로 바꾸어 중복을 제거했을 때, 중복이 존재하여 방문하지 않은 칸이 있는지 확인한다.

3) 마지막 칸과 출발한 칸의 번호 차이가 (2,1) 이거나 (1,2) 인지 확인한다.

 

이 3가지 조건들을 만족했을 때 'Valid'를 출력할 수 있게 된다.

#1331

def check_valid(now, dest):
  if abs(ord(now[0]) - ord(dest[0])) == 2 and abs(int(now[1]) - int(dest[1])) == 1:
    return 1
  elif abs(ord(now[0]) - ord(dest[0])) == 1 and abs(int(now[1]) - int(dest[1])) == 2:
    return 1
  else:
    return 0

sqrs = []
now = input()
sqrs.append(now)

cnt = 1
for i in range(35):
  dest = input()
  sqrs.append(dest)

  if check_valid(now,dest) == 1:
    cnt += 1
    now = dest
  else:
    break

if cnt == 36 and len(set(sqrs))== 36 and check_valid(sqrs[0],sqrs[-1]):
  print('Valid')
else:
  print('Invalid')