[CodeTree/Python] 화면에 출력

문제

화면에 출력

화면에 문자가 하나 입력되어있습니다. 다음의 연산을 통해 문자를 s개로 만들어 보려고 합니다.

• 화면에 있는 모든 문자를 복사해서 클립보드에 저장합니다.
• 클립보드에 있는 모든 문자를 화면에 붙여넣기합니다.
• 화면에 있는 문자중 하나를 삭제합니다.

클립보드의 내용은 항상 덮어씌어 지며, 클립보드의 문자는 삭제할 수 없고, 클립보드의 문자를 화면에 붙여넣으면 문자가 추가가됩니다.

클립보드가 비어있으면 2번연산을 실행할 수 없으며, 일부만 복사할 수 없습니다.

이러한 연산을 통해 문자를 s개 만드는데 필요한 최소 연산 횟수를 구하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에 s가 주어집니다.

• 2 ≤ s ≤ 1,000

출력 형식

문자열을 s개 만들기 위해 필요한 최소 연산 횟수를 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이

from collections import deque
s = int(input())
def char(s):
    # 큐 생성: (화면 문자 카운트, 클립보드 문자 카운트, 연산 카운트)
    Q = deque([(1, 0, 0)]) # 초기 화면에 문자 1개
    visit = [(1, 0)] # 화면, 클립보드 방문 리스트

    while Q:
        screen, clipboard, count = Q.popleft()

        if screen == s:
            return count

        # 복사
        if (screen, screen) not in visit: # screen의 값을 클립보드에 복사하므로 클립보드의 값도 screen
            visit.append((screen, screen))
            Q.append((screen, screen, count + 1))

        # 붙여넣기
        if clipboard > 0 and (screen + clipboard, clipboard) not in visit:
            visit.append((screen + clipboard, clipboard))
            Q.append((screen + clipboard, clipboard, count + 1))

        # 삭제
        if screen > 1 and (screen - 1, clipboard) not in visit:
            visit.append((screen - 1, clipboard))
            Q.append((screen - 1, clipboard, count + 1))

print(char(s))

    BFS를 사용하여 모든 가능한 경우를 돌면서 목표값에 도달하는 데 필요한 최소 연산 횟수를 찾는 문제이다. 목표값에 도달하기 위한 카운트를 큐에 함께 세팅하였고, 초기 상태에서 화면에 문자가 하나 주어지므로 (1, 0, 0)을 초기값으로 지정했다.

    각 기능에 따른 노드가 방문 리스트에 존재하지 않으면, 방문 표시를 하고 큐에 카운트값을 추가하여 큐에 추가하여 모든 경우의 수를 탐색하였다. 큐를 돌다가 화면 문자의 수가 목표값 s가 되는 경우 count를 리턴하도록 함수를 생성하였다.