[Baekjoon] 2447번 : 별 찍기 - 10 / 11729번 : 하노이의 탑

# 별 찍기

2447번: 별 찍기 - 10

문제에서 주어진 사이즈, 패턴과 일치하도록 별을 출력하면 되는 문제이다.

주어진 사이즈의 세로를 1/3로 나누어 한 줄씩 재귀적으로 패턴을 채워준다.

 

import sys

def pattern(size):
    # 사이즈가 1이 되면 *만 추가
    if size == 1:
        return ['*']

    # 전체 사이즈의 1/3씩 패턴을 만들기 위해 작은 사이즈에서 만든 패턴을 재귀적으로 호출
    patterns = pattern(size//3)
    new_pattern = [] # 새로 만들 패턴을 저장할 리스트

    for p in patterns:
        new_pattern.append(p*3)
    for p in patterns:
        # 가운데가 비어있도록 넣어줌
        new_pattern.append(p+' '*(size//3)+p)
    for p in patterns:
        new_pattern.append(p * 3)

    return new_pattern

n = int(sys.stdin.readline().strip())
print('\n'.join(pattern(n)))

 

# 하노이의 탑 ⭐

11729번: 하노이 탑 이동 순서

하노이의 탑은 재귀함수로 풀 수 있는 대표적인 문제라고 하니 잘 기억해 둬야 한다.

move = []

def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:  # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
        move.append((from_pos, to_pos))
        return

    # 원반 n -1개를 aux_pos으로 이동(to_pos를 보조 기둥으로)
    hanoi(n - 1, from_pos, aux_pos, to_pos)
    # 가장 큰 원반을 목적지로 이동
    move.append((from_pos, to_pos))

    # aux_pos에 있는 원반 n -1개를 목적지로 이동(from_pos를 보조 기둥으로)
    hanoi(n - 1, aux_pos, to_pos, from_pos)

n = int(input())
count = 0
hanoi(n, 1, 3, 2)

print(len(move))
for i in range(len(move)):
    print(move[i][0], move[i][1])

 

 

⭐ 하노이의 탑에 대해 알아보기

 

먼저 입력 받은 원반의 개수가 1이면 보조 기둥을 사용할 필요 없이, 시작 지점에서 목표 지점으로 옮기면 이동이 완료된다.

def hanoi(원반개수, 시작, 목표, 보조):
	if 원반개수 == 1:
    	print(시작, '->', 목표)
        return #함수 종료

 

하지만 원반이 3개 이상인 경우엔 보조 기둥을 사용해야만 한다.

여기서 중요한 것은 가장 큰 원반을 제외한 나머지 원반들을 보조 기둥으로 보내는 것이다.

즉, 원반이 2개일 때는 1개를, 3개일 때는 2개를 n개일 때는 n-1개를 옮기는 것이다.

이를 코드로 나타내면 다음과 같다.

 

hanoi(원반개수 -1, 시작, 보조, 목표) #보조기둥이 목표가 됨

 

다음으로 시작 기둥에 남아있는 가장 큰 원반을 목표 기둥으로 옮긴다.

print(시작, '->', 목표)

 

이렇게 가장 큰 원반이 옮겨지고 나머지는 방금 옮긴 큰 원반을 제외하고 다시 반복한다.

여기서 이전 과정에서의 보조기둥은 시작 기둥이 되고 시작 기둥은 보조 기둥이 된다.

코드 또한 아래와 같이 변경하여 표현한다.

 

hanoi(원반개수 -1, 보조, 목표, 시작) # 보조와 시작이 바뀜

 

이렇게 재귀적으로 모든 원반을 옮기면 된다.

전체 코드는 이렇다.

def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:  # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
        print(from_pos, '->', to_pos)
        return

    # 원반 n -1개를 aux_pos으로 이동(to_pos를 보조 기둥으로)
    hanoi(n - 1, from_pos, aux_pos, to_pos)
    # 가장 큰 원반을 목적지로 이동
    print(from_pos, '->', to_pos)

    # aux_pos에 있는 원반 n -1개를 목적지로 이동(from_pos를 보조 기둥으로)
    hanoi(n - 1, aux_pos, to_pos, from_pos)

 

나는 어떻게 해야할지 전혀 감이 안잡혀서 아래 영상을 참고해서 공부했다.