[백준] 1331 나이트 투어 (Baekjoon Problem 1331: Knight Tour)

문제 출처

 

[문제 요약]

나이트 투어의 정의는 체스에서의 나이트가 모든 칸을 정확히 한번찍 방문하고 마지막으로 방문하는 칸에서 시작점으로 돌아오는 경로를 의미한다.

 

아래와 같은 6*6 체스판에서 나이트 투어를 할 때, 36개의 입력이 나이트 투어의 정의를 만족하는지를 판별하면 된다.

가로는 알파벳이, 세로는 숫자로 표기되어 "1A", "2A", ..., "6F"까지 나이트가 방문한 칸을 표기할 수 있다.

6x6 체스판

[풀이]

나이크는 총 3칸을 움직이는데 아래처럼 방향은 자유롭게 아래처럼 움직인다.

• 가로 1칸 -> 세로 2칸
• 가로 2칸 -> 세로 1칸

따라서 원래 있던 자리에서 새롭게 간 자리가 나이트 움직임인지를 판별하려면

알파벳 사이의 간격과 숫자 사이의 간격의 합이 3이 되는지를 보면 된다.

 

그리고 마지막으로 도착한 곳 역시 맨 처음 시작점과 비교해 나이트가 갈 수 있는지를 보면 된다.

[유의할 점 #1]

알파벳과 숫자간의 간격이라고 표현한 이유는 말이 항상 오른쪽으로 혹은 위쪽으로만 가지 않기 때문이다.

새로 간 곳이 D4 -> C2처럼 알파벳이나 숫자가 줄어들 수 있다.

따라서 abs 함수 (absolute) 값을 사용할 것

 

[유의할 점 #2]

입력이 총 36개가 들어온다. 중간에 나이트가 가지 못하는 경로라고 판별을 마쳐도 입력을 다 받지 않은 상태에서 Invalid라고 프린트하고 룹을 (break를 사용해서) 빠져나오면 문제가 생겼었다.

 

[유의할 점 #3]

사소한 점들인데 시작점이 항상 "A1"이 아니라는 점, 그리고 프린트 하는 Valid와 Invalid 맨 앞에 대문자이다. 소문자로 프린트하게 했다가 틀렸었다.

[파이썬 3 코드]

def check_alp(alp: str, alp2: str):
    # returns interval between number
    alps = ["A", "B", "C", "D", "E", "F"]
    idx1 = alps.index(alp)
    idx2 = alps.index(alp2)
    if abs(idx2 - idx1) == 1:
        return 1
    elif abs(idx2 - idx1) == 2:
        return 2
    else:
        return -1 # invalid

def check_num(num:int, num2: int):
    if abs(num2 - num) == 1:
        return 1
    elif abs(num2 - num) == 2:
        return 2
    else:
        return -1

if __name__ == "__main__":
    n = 36

    # knight가 갈 수 있는곳인지 확인
    # 마지막에서 처음으로 올 수 있는지 확인

    path_set = set()

    # "A1" 이 항상 시작임 <- 아님
    # 미리 다 입력을 받고 처리해야함 <- 이건 아닌데 입력이 남은 상태에서 프린트는 ㄴㄴ
    # 어이없게도 capital 까먹어서 틀림 ㅋㅋㅋ
    start_word = input()
    prev_word = start_word
    path_set.add(prev_word)
    to_print = "Valid"
    for k in range(1, n):
        cur_word = input()
        path_set.add(cur_word)
        alp_res = check_alp(prev_word[0], cur_word[0])
        num_res = check_num(int(prev_word[1]), int(cur_word[1]))
        if alp_res + num_res != 3:
            to_print = "Invalid"
            # break

        prev_word = cur_word

    # prev_word에 가장 마지막 element가 저장되어있음
    interval_sum = check_alp(prev_word[0], start_word[0]) + check_num(int(prev_word[1]), int(start_word[1]))
    if interval_sum != 3:
        to_print = "Invalid"
    else:
        # 중복있는지 확인
        if len(list(path_set)) != n:
            to_print = "Invalid"

    print(to_print)