[python]파이썬 나이트 투어 재귀 알고리즘 Knight's Tour Problem recursive

Knight's Tour Problem 

체스판에서 기사(Knight)말의 움직임은 아래와 같다. 임의의 위치에 놓여진 기사를 움직여서 모든 64개의 격자를 모두 방문하도록 기사말을 옮기는 방법을 계산하라. 단, 기사가 이미 방문한 격자는 다시 방문하지 않는다. 

 

풀이 과정

1. 나이트가 움직일 수 있는 방향 저장 [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], -1, -2]
2. 초기 위치에서 나이트가 갈 수 있는 방향으로 전진. 
3. 체스판 안의 위치인지 확인.
4. 한번도 가지 않은 길이면 전진가능 mark배열에 갔던곳 표시 .
5. 한번 갔던 길이면 다시 후진 다른 경로 찾음.
6. 위의 과정을 반복하며 갈 수 있는 길로 전진, 갈 수 없으면 되돌아오기를 반복한다. 

 

코드 구현 

입력

입력은 표준입력을 사용한다. 입력은 𝑡 개의 테스트 케이스로 주어진다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 𝑡가 주어진다. 두 번째 줄부터 𝑡 개의 줄에 는 한 줄에 한 개의 테스트 케이스에 해당하는 네 개의 정수 𝑚 𝑛 𝑎 𝑏 (2 ≤ 𝑚, 𝑛 ≤ 8, 1 ≤ 𝑎 ≤ 𝑚, 1 ≤ 𝑏 ≤ 𝑛 )가 입력된다. 첫 번째 정수 𝑚 은 체스판의 행의 개수를 나타내고, 두 번째 정수 𝑛 은 열 의 개수를 나타낸다. 또한 두 정수 𝑎, 𝑏는 기사의 처음 출발한 셀의 위치 ⟨𝑎, 𝑏⟩를 나타낸다. 각 정수들 사이에는 한 개의 공백이 있으며, 잘못된 데이터가 입력되는 경우는 없다.

 

출력 

출력은 표준출력을 사용한다. 각 테스트 케이스에 해당하는 출력에는 주어진 체 스판에서 기사가 초기 셀에서 출발하여 체스판의 모든 다른 셀을 방문하는 경로가 존재하면 1 을 출력하고 그렇지 않으면 0 을 출력한다. 경로가 존재하는 경우에는 기사가 출발하는 셀에 1 번을 부여하고, 그 다음으로 옮겨가는 셀들에는 순서대로 2, 3, 4, … 등으로 부여하여, 이러한 번호 를 체스판의 첫 번째 행부터 한 줄에 한 행씩 출력한다. 또한 같은 행에서는 첫 번째 열부터 마 지막 열까지 순서대로 출력한다. 같은 줄에 출력되는 각 정수들 사이에는 한 개의 공백을 둔다

 

풀이 방법

 

1) 나이트 말의 움직임을 지정
    row = [1, 2, 2, 1, -1, -2, -2, -1]
    col = [-2, -1, 1, 2, 2, 1, -1, -2]

 

2) 재귀 아이디어

• 나이트가 갈 수 있는 8 방향으로 모두 돌아보면서 간적이 있는 길인지 확인해보기 
• 만약 방문한적이 있다면 다른 방향으로 다시 시도 
• 방문한적이 없다면 재귀 호출로 그 자리 탐색 
• 반복 

3) step으로 이동을 나타낸다 . 

step변수로 나이트의 이동경로를 나타낸다. 

def knight(start_x, start_y, row_size, col_size, step):
    # 나이트 말 움직임
    row = [1, 2, 2, 1, -1, -2, -2, -1]
    col = [-2, -1, 1, 2, 2, 1, -1, -2]
    
    # 디버깅: 현재 위치와 스텝 출력
    print(f"Step {step}: at ({start_x+1}, {start_y+1})")
    
    # 모든 칸을 다 방문했으면 return 1
    if step == row_size * col_size:
        return 1
    
    # 가능한 이동 경로를 확인
    for i in range(8):
        pre_x = start_x + row[i]
        pre_y = start_y + col[i]
        
        # 체스판 범위 안에 있고, 아직 방문하지 않은 칸인지 확인
        if 0 <= pre_x < row_size and 0 <= pre_y < col_size and marks[pre_x][pre_y] == -1:
            marks[pre_x][pre_y] = step + 1  # 방문 기록
            # 디버깅: 이동한 좌표 출력
            print(f"Moving to ({pre_x+1}, {pre_y+1})")
            
            # 나이트 투어 재귀 호출
            if knight(pre_x, pre_y, row_size, col_size, step + 1):
                return 1
            # 백트래킹: 방문 기록 취소
            marks[pre_x][pre_y] = -1
            # 디버깅: 되돌아오는 좌표 출력
            print(f"Backtracking from ({pre_x+1}, {pre_y+1})")
    
    return 0  # 모든 이동 경로가 막힌 경우 0 반환

# 테스트 케이스 입력
test_case = int(input())
for _ in range(test_case):
    row_size, col_size, start_x, start_y = map(int, input().split())
    start_x -= 1  # 0-based 인덱스로 변환
    start_y -= 1
    
    # 방문 기록을 저장할 2차원 배열 초기화
    marks = [[-1] * col_size for _ in range(row_size)]
    marks[start_x][start_y] = 1  
    
    # 나이트 투어 시작
    success = knight(start_x, start_y, row_size, col_size, 1)
    
    # 결과 출력
    print(success)
    if success:
        for row in marks:
            print(" ".join(map(str, row)))

문제 

테스트 케이스 

1

7 5 4 3 일때 무한재귀에 빠지는 문제가 있다.