알고리즘 분류
- 구현
- 시뮬레이션
문제
나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다.
영식이는 6×6 체스판 위에서 또 다른 나이트 투어의 경로를 찾으려고 한다. 체스판의 한 칸은 A, B, C, D, E, F 중에서 하나와 1, 2, 3, 4, 5, 6 중에서 하나를 이어 붙인 것으로 나타낼 수 있다. 영식이의 나이트 투어 경로가 주어질 때, 이것이 올바른 것이면 Valid, 올바르지 않으면 Invalid를 출력하는 프로그램을 작성하시오.
입력
36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다. 체스판에 존재하는 칸만 입력으로 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
처음 풀이에서는 6 * 6의 0으로 되어있는 보드를 만들어주었다. 이동하는 칸마다 이미 이동한 곳인지, 이동 사정 거리가 맞는지 확인해주고 맞다면 1로 바꾸어 모든 칸을 이동했다면 Valid 아니라면 Invalid를 출력하는 방식으로 코드를 작성했다.
해당 코드는 정답이었지만, 다른 정답 코드들을 확인해보니 set()함수와 파이썬의 인덱스 특성을 이용해 좀 더 직관적이고 간소화된 코드를 만들 수 있었다. 언어의 기본적인 걸 좀 더 알면 작성할 수 있는 코드라 생각한다.
소스 코드
Python 1
board = [[0] * 6 for _ in range(6)]
knight = [(-2, -1), (-2, 1), (2, -1), (2, 1),
(-1, -2), (-1, 2), (1, -2), (1, 2)]
def moveKnight(last):
global move
vaild = True
for item in knight:
if ord(move[0]) - ord('A') - item[0] == ord(last[0]) - ord('A') and int(move[1]) - 1 - item[1] == int(last[1]) - 1:
vaild = True
break
else:
vaild = False
return vaild
start = input()
last = start
board[ord(start[0]) - ord('A')][int(start[1]) - 1] = 1
vaild = True
for _ in range(35):
move = input()
if board[ord(move[0]) - ord('A')][int(move[1]) - 1] == 1:
vaild = False
break
else:
if vaild:
vaild = moveKnight(last)
board[ord(move[0]) - ord('A')][int(move[1]) - 1] = 1
last = move
if vaild:
vaild = moveKnight(start)
if vaild:
print("Valid")
else:
print("Invalid")
Python 2
# 1331번 나이트 투어
board = []
valid = True
for _ in range(36):
board.append(input())
# set : 집합 처리를 위한 함수
if len(set(board)) != 36:
valid = False
# list[-1] : 리스트 뒤에서 첫 번째 요소
for i in range(36):
diffRow = abs(ord(board[i][0])-ord(board[i-1][0]))
diffCol = abs(int(board[i][1])-int(board[i-1][1]))
if (diffRow == 1 and diffCol == 2) or (diffRow == 2 and diffCol == 1):
continue
else:
valid = False
if valid:
print("Valid")
else:
print("Invalid")
Ghost