[python]파이썬 나이트 투어 반복 알고리즘 Knight's Tour Problem iteration

https://codinghago.tistory.com/55

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

 

앞서 살펴보았던 나이트 투어 알고리즘을 재귀함수가 아닌 반복문으로 해결해 보려고 한다. 

stack을 사용하면 반복문으로 해결할 수 있다. 

 

스택(STACK)

스택은 자료구조의 한 형태로, LIFO(Last In First Out) 후입선출의 원칙에 따라 데이터를 관리한다. 즉,  가장 마지막에 쌓은 데이터를 가장 먼저 꺼내 사용하는 방식이다. 

 

파이썬에서는 list[]로 이미 구현이 되어 있어서 list를 사용하면 된다. 

파이썬 스택 사용법

- list.append() : 괄호 안의 요소를 리스트 맨 뒤에 넣음 

stack = [1,2,3,4,5]
stack.append(6)
=> s[1,2,3,4,5,6]

 

- list.pop() : 리스트의 맨 뒤의 요소를 빼고 리스트에서 삭제한다. 

stack = [1,2,3,4,5]
print(stack.pop())
=> 5

 

입력과 출력은 이전 문제와 동일하다 

재귀가 아닌 반복문으로 하기 위해서 stack에 이동경로를 저장해두고 꺼내서 써야한다. 기본적인 해결방법은 저번과 동일하지만 이번에는 다음에 이동할 경로가 조건을 만족할 경우 stack에 현재 자리와 다음에 이동할 경로를 저장하는 것으로 재귀를 대신할 것이다. 현재 자리를 stack에 함께 저장하는 이유는 백트랙킹을 위해서이다. 만약 조건을 만족해서 나이트를 이동시켰는데 그 이후에 경로가 막히면 다시 뒤로 돌아와야하기 때문이다. 

 

재귀함수에서는 함수가 return으로 돌아오면 그 다음 반복을 이어갈 수 있었지만 반복문으로 구현하면 따로  다음 반복은 어디부터 시작해야하는지 알려주기 위해 move_idx를 stack에 같이 저장해줬다. 

 

 

def kight(start_x, start_y, row_size, col_size):
     # 나이트 말 움직임
    row = [1, 2, 2, 1, -1, -2, -2, -1]
    col = [-2, -1, 1, 2, 2, 1, -1, -2]

    # 방문 기록을 저장할 2차원 배열 초기화
    marks = [ [-1] * col_size  for i in range(row_size)]
    marks[start_x][start_y] = 1

    # stack 초기화 
    move_idx = 0 
    stack = [(start_x, start_y, 1, 0)]

    # 나이트 여행 시작! 
    while stack : 
        # stack에 있는 값 꺼내오기
        cur_x, cur_y, step, move_idx = stack.pop()

        # 체스판 크기만큼 돌았다면 해를 찾았음으로 종료 
        if step == row_size*col_size:
            return 1, marks
        
        while move_idx < 8:
            pre_x = cur_x + row[move_idx]
            pre_y = cur_y + col[move_idx]

            # 체스판 밖이 아니고 한번도 간적 없는 길인지 확인
            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

                # Stack에 현재 자리 저장, 움직인 자리 저장
                stack.append((cur_x, cur_y, step, move_idx + 1))
                stack.append((pre_x, pre_y, step+1, 0))
                break
            move_idx += 1
        
        if move_idx == 8: 
            marks[cur_x][cur_y] = -1

    # 해를 못찾으면 0 return 
    return 0, marks


test_case = int(input())
for _ in range(test_case):
    row_size, col_size, start_x, start_y = map(int, input().split())
    start_x -= 1
    start_y -= 1
    success, marks = kight(start_x, start_y, row_size, col_size)
    print(success)
    if success:
        for row in marks:
            print(" ".join(map(str, row)))