BOJ 1331. 나이트 투어

- 구현, 시뮬레이션

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

1331번: 나이트 투어

 

- 나이트 이동 : [2, 1] 혹은 [1, 2]씩만 이동(좌표 음수, 양수 상관 없이)

-> 1. 현재 좌표와 이전 좌표간의 거리가 결국 다 일정함 (2d distance 개념 사용)

    sqrt((x2-x1)^2 + (y2-y1)^2)

-> 2. 마지막 좌표에서 시작 좌표로 돌아가야 끝나기 때문에 마지막에 1번의 개념 한번 더 사용해서 확인 

 

#입력, 빈 체스판 생성
chess_arr = [[0]*6 for _ in range(6)]
chess = [input() for _ in range(36)]

#모든 좌표 다 돌아야하기 때문에 입력값이 다 고유한 좌표를 가져야함
if len(set(chess)) == 36:
    for i in range(36):
    	#앞으로 사용할 변수를 처음 좌표값에서 선언
        if i == 0:
            now = chess[i]
            prev = chess[i]

            x, y = ord(prev[0]) - 65, int(prev[1]) - 1
            #방문 표시
            chess_arr[x][y] = 1
            
        elif 0 < i < 35:
            now = chess[i]
            x1,y1 = ord(now[0]) - 65, int(now[1]) - 1
            x2,y2 = ord(prev[0]) - 65, int(prev[1]) - 1
			
            #나이트 이동 계산
            dist = (((x2-x1) ** 2) + ((y2-y1) ** 2)) ** 0.5

            if dist == (5 ** 0.5) and chess_arr[x1][y1] == 0:
                flag = 1
                chess_arr[x1][y1] = 1
                prev = now 
            else:
            	# 만족 안 할 때 바로 멈춘다.
                flag = 0
                break
		
        #마지막 지점에서 시작 지점으로 돌아가기 위한 부분
        else:
            now = chess[i]
            start_point = chess[0]

            x1,y1 = ord(now[0]) - 65, int(now[1]) - 1
            x2, y2 = ord(start_point[0]) - 65, int(start_point[1]) - 1

            dist = (((x1-x2) ** 2) + ((y1-y2) ** 2)) ** 0.5
            if dist == (5 ** 0.5):
                flag = 1
            else:
                flag = 0
else:
    flag = 0

if flag == 1:
    print("Valid")
else:
    print("Invalid")