문제요약
나의 코드 및 설명 - DFS 활용
- DFS를 활용하여 문제를 해결하였다.
def dfs(depth, temp):
global a,b
if temp >= b:
if temp == b:
result.append(depth)
return
dfs(depth+1, temp*2)
dfs(depth+1, int("".join(map(str, (list(map(int, str(temp)))+[1])))))
a, b = map(int, input().split())
result = []
dfs(0,a)
if result:
print(min(result)+1)
else:
print(-1)
다른 코드 및 설명 - BFS 활용
- BFS를 활용하여 문제를 해결하였다.
- 큐에 다음 숫자와 연산의 개수를 추가한다.
from collections import deque
def bfs(a,b):
queue = deque()
queue.append((a,1))
while queue:
next_num, depth = queue.popleft()
if next_num > b:
continue
if next_num == b:
result.append(depth)
queue.append((int(str(next_num)+"1"),depth+1))
queue.append((next_num*2, depth+1))
a,b = map(int, input().split())
result = []
bfs(a,b)
if result:
print(min(result))
else:
print(-1)
피드백
비슷한 유형의 문제를 여러 번 풀어봤었고, DFS를 활용하여 문제를 간단하게 해결하였다.
'Baekjoon > DFS와 BFS' 카테고리의 다른 글
🥇[백준] 1941 소문난 칠공주 (골드3) / DFS, BFS, 백트래킹 (0) | 2023.05.03 |
---|---|
🥇[백준] 2146 다리 만들기 (골드3) / BFS (0) | 2023.05.01 |
🥇[백준] 1987 알파벳 (골드4) / DFS, list, set, dict 시간복잡도 정리 (0) | 2023.05.01 |
[백준] 1743 음식물 피하기 (실버1) / DFS (1) | 2023.04.30 |
🥇[백준] 10026 적록색약 (골드5) / BFS (0) | 2023.04.30 |