BFS - 스타트링크 [5014번]
2022. 7. 18. 16:55ㆍ2022/BaekJoon_알고리즘
어제도 BFS 문제를 풀면서 아래 첫번째 코드 처럼 q에 [현재 층수, 움직인 횟수] 형태로 append하였더니 시간초과가 나왔다.
deque로 BFS 문제를 풀때는 방문 여부를 처리하는 부분이 별개로 필요하다는 것을 다시 한번 깨닫게 하였다.
F, S, G, U, D = map(int, input().split())
from collections import deque
q = deque([(S, 0)])
tmp = []
if U > 0:
tmp.append(U)
if D > 0:
tmp.append(-1 * D)
chk = False
while q:
floor, cnt = q.popleft()
if floor == G:
chk = True
break
for a in tmp:
f = floor + a
if 1 <= f <= F:
q.append((f, cnt+1))
if chk == False:
print("use the stairs")
아래 코드가 테스트를 통과한 코드이다.
F, S, G, U, D = map(int, input().split())
from collections import deque
q = deque([S])
visited = [0 for _ in range(F+1)]
tmp = []
if U > 0:
tmp.append(U)
if D > 0:
tmp.append(-1 * D)
chk = False
while q:
floor = q.popleft()
if floor == G:
print(visited[floor])
chk = True
break
for a in tmp:
f = floor + a
if 1 <= f <= F and not visited[f]:
q.append(f)
visited[f] = visited[floor]+1
if chk == False:
print("use the stairs")
'2022 > BaekJoon_알고리즘' 카테고리의 다른 글
BFS - 토마토 [ 7569번 ] (0) | 2022.07.22 |
---|---|
BFS - 빙산 [ 2573번 ] (0) | 2022.07.20 |
BFS - 안전영역 (0) | 2022.07.18 |
DFS - 촌수계산 [2644번] (0) | 2022.07.17 |
BFS - 숨바꼭질 [1697번] (0) | 2022.07.15 |