[SWEA] 5247. [파이썬 S/W 문제해결 구현] 6일차 - 연산 [D4]
📚 문제
📖 풀이
최단거리를 구하는 문제이므로 BFS문제이다.
BFS로 다음 노드들로 깊어질 때마다 연산 횟수가 1 증가하니, size로 bfs를 탐색하기 전에 큐에 있는 개수를 세고, 매번 일정한 깊이의 노드들을 시행한 후 다음 노드들을 시행하기 전에 횟수들을 1 늘려준다. 그러면 깊이마다 탐색할 수 있다.
값이 나오면 종료시키기 위해 함수에 작성한 후 return으로 종료한다.
📒 코드
from collections import deque
def in_range(x): # 범위를 나타내는 함수
return 0 < x <= 1000000
def bfs():
visited = [0 for _ in range(1000001)] # 연산의 중간과정은 항상 백만 이하의 자연수
que = deque()
que.append(n)
d = 0 # 연산 횟수
while que:
size = len(que)
for i in range(size):
v = que.popleft()
if v == m:
return d
for i in range(3):
if not(in_range(v + cal[i])) or visited[v + cal[i]]:
continue
visited[v + cal[i]] = 1
que.append(v + cal[i])
if in_range(v * 2) and visited[v * 2] == 0: # 곱하기는 따로 작성한다.
visited[v * 2] = 1
que.append(v * 2)
d += 1
t = int(input())
cal = [1, -1, -10] # +, - 계산할 것들을 담아준다.
for tc in range(1, 1 + t):
n, m = map(int, input().split())
print(f'#{tc} {bfs()}')
🔍 결과
Author And Source
이 문제에 관하여([SWEA] 5247. [파이썬 S/W 문제해결 구현] 6일차 - 연산 [D4]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/SWEA-5247.-파이썬-SW-문제해결-구현-6일차-연산-D4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)