[백준 파이썬] 1463 1로 만들기

📌문제 출처

솔브닷 클래스 3+ 단계
https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

❓ 문제

❗ 풀이

• bfs 활용

📗 풀이 코드

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
def bfs(n):
    stack = deque([[n,0]])
    cnt = 0
    while stack:
        i,cnt = stack.popleft()
        if i==1:
            return cnt
        cnt += 1
        if (not i%3)and (not visited[i//3]):
            stack.append([i//3,cnt])
            visited[i%3] = 1
        if (not i%2)and (not visited[i//2]):
            stack.append([i//2,cnt])
            visited[i%2] = 1
        if (not visited[i-1]):
            stack.append([i-1,cnt])
            visited[i-1] = 1
n = int(input())
visited = defaultdict(int)
print(bfs(n))

📗 코드 해설

• bfs에 입력값 n을 넣고 시작하여 1이 될 때 까지 중복을 배제하고 계속 연산해갈 것이다.
• stack에는 while 문을 돌며 [새로운 연산 결과, 연산 횟수]를 넣어줄 것이다.
• visited는 defaultdict(int)로 연산을 한 적이 있으면 1로 넣어줄 것이다.
• 조건에 나온 연산이 가능하다면 새롭게 stack에 추가하고 그 연산결과가 1이 될 때까지 while문을 반복한다.