하노이의 탑, 8퀸 문제

Preface

 

거의 두 달 만에 글을 작성한다.

 

개발 공부를 시작한 뒤로 이렇게 오래 공부를 쉬었던 적은 처음인 것 같다.

 

그동안 이런저런 일들이 있었다.

 

기말고사를 친 후 무사히 2학기를 마쳤고, 여자친구가 생겨 이곳 저곳 놀러다니며 데이트도 했다.

 

정말 오랜만에 사귄 여자친구인 탓인지 모든 정신이 팔려 시간 가는 줄도 모르고 두 달을 보낸 것 같다.

 

그런데 연말이 되고 주변에서 목표를 이루기 위해 노력하는 친구들을 보니 문득 정신이 들었고, 이렇게 허송세월을 보낼 수는 없다는 생각이 뇌리를 스쳤다.

 

이제 며칠 후면 스물 셋이 되고 졸업도 가까워졌다는 조바심에 서둘러 책을 펴 공부를 시작했지만, 너무 오랜만에 공부를 하는 탓인지, 내용 자체가 어려운 탓인지 이해가 잘 되지 않았고, 기본적인 내용도 기억이 잘 나지 않았다.

 

이번 장의 주된 내용인 재귀 알고리즘은 아무리 읽어보고 한 줄 한 줄 코드를 분석해봐도 왜 이렇게 작성한 것인지, 출력값이 왜 이렇게 나오는지 이해할 수 없었다.

 

그래서 일단 책에 있는 코드를 그대로 작성하여 블로그에 올려놓기로 했다.

 

이 글을 업로드한 후 파이썬 기초 카테고리에 있는 모든 글을 복습한 후 다시 코드를 분석해 볼 계획이다.

---

 

1. 하노이의 탑

 

 

- 하노이의 탑 : 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제

 

 

- 하노이의 탑 코드

def move(no: int, x: int, y: int) -> None:
    # no: 옮겨야 할 원반 개수, x: 시작 기둥의 번호, y: 목표 기둥의 번호

    if no > 1:
        move(no - 1, x, 6 - x - y)

    print(f'원반 [{no}]을 {x} 기둥에서 {y} 기둥으로 옮깁니다.')

    if no > 1:
        move(no - 1, 6 - x - y, y)


print('하노이의 탑을 구현합니다.')
n = int(input('원반의 개수를 입력하세요: '))

move(n, 1, 3)

 

---

 

2. 8퀸 문제

 

 

- 8퀸 문제 : 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 x 8 체스판에 배치하는 문제

→ 퀸은 가로, 세로, 대각선 어디든 직선 이동할 수 있음

 

 

- 규칙

1) 각 열에 퀸을 1개만 배치

2) 각 행에 퀸을 1개만 배치

3) 대각선 배치 고려

 

 

- 규칙 1을 적용한 코드

pos = [0] * 8


def put() -> None:
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()


def set(i: int) -> None:
    for j in range(8):
        pos[i] = j
        if i == 7:
            put()
        else:
            set(i + 1)


set(0)

 

 

- 분기 작업 : 차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법

 

 

- 분할 정복(해결)법 : 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법

 

 

- 규칙 2를 적용한 코드

pos = [0] * 8
flag = [False] * 8


def put() -> None:
    for i in range(8):
        print(f'{pos[i]:2}', end='')
    print()


def set(i: int) -> None:
    for j in range(8):
        if not flag[j]:
            pos[i] = j
            if i == 7:
                put()
            else:
                flag[j] = True
                set(i + 1)
                flag[j] = False


set(0)

 

 

- 한정 작업 : 필요하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법

 

 

- 분기 한정법 : 분기 작업과 한정 작업을 조합하여 문제를 풀이하는 방법

 

 

- 모든 규칙을 적용한 코드

pos = [0] * 8
flag_a = [False] * 8
flag_b = [False] * 15
flag_c = [False] * 15


def put() -> None:
    for j in range(8):
        for i in range(8):
            print('■' if pos[i] == j else '□', end=' ')
        print()
    print()


def set(i: int) -> None:
    for j in range(8):
        if (not flag_a[j]
                and not flag_b[i + j]
                and not flag_c[i - j + 7]):
            pos[i] = j
            if i == 7:
                put()
            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
                set(i + 1)
                flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False


set(0)