DFS/BFS 정수 a를 k로 만들기

• 문제 분석 요약

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

• 알고리즘 설계

# k+1만큼 0으로 된 리스트 graph 생성. (k로 가기까지의 최소 연산 수 저장, 방문했던 숫자인지 확인)

# 초기값이 들어간 큐 생성.

# 큐에서 popleft하여 두가지 경우의 수 (1번 연산, 2번 연산)가 k를 넘지 않고 방문하지 않았다면 큐에 append.

# popleft했을 때 k와 숫자가 같다면 break로 반복문 종료.

• 코드

• 느낀 점

최소 연산 수를 구하는 문제로 bfs가 더 적합.

리스트를 방문확인과 최소연산 수 카운트로 씀.

for문으로 2가지 연산 경우의 수를 한번에 적용