728x90
반응형
※ 문제링크
해당 문제는 BFS를 활용하여 해결할 수 있는 문제였다. 주의해야할 점은 건물의 최소 층수가 1층이라는 점과 출발층과 목표층이 같을수 있다는 점이었다. 그 이외에는 BFS와 queuq자료구조를 활용하면 비교적 쉽게 해결할 수 있는 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다.
1. 입력받은 값들을 따로 숫자형태로 저장해준다.
2. 한번에 움직일 수 있는 경우의 수들을 확인하고, 조건에 맞으면 queue자료구조에 넣고 추출하여 방문여부를 확인하는 방식으로 작동하는 BFS함수를 작성해준다.
3. 입력받은 값들을 바탕으로 결과값을 출력해준다.
from collections import deque
F, S, G, U, D = map(int, input().split()) # F: 총 건물의 층수 / S: 출발위치 / G: 가야하는 층수
# U:한번에 올라갈 수 있는 층수 / D: 한번에 내려갈 수 있는 층수
def bfs(F, S, G, U, D):
queue = deque()
visited = [False for _ in range(F+1)]
queue.append(S)
visited[S] = True
if S == G: # 출발점과 목표점이 같을 때는 0을 출력
return 0
cnt = 0
while queue:
for _ in range(len(queue)):
floor = queue.popleft()
floor_up = floor + U # 올라가는 경우의 수 체크
floor_down = floor - D # # 내려가는 경우의 수 체크
if floor_up == G or floor_down == G:
return cnt + 1
if 0 < floor_up <= F and visited[floor_up] == False: # 조건만족시 queue에 추가 및 방문기록
queue.append(floor_up)
visited[floor_up] = True
if 0 < floor_down <= F and visited[floor_down] == False: # 조건만족시 queue에 추가 및 방문기록
queue.append(floor_down)
visited[floor_down] = True
cnt += 1
return 'use the stairs' # 탐색을 완료하고도 목표점에 도달 불가시 출력
ans = bfs(F, S, G, U, D)
print(ans)
P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 2003번 수들의 합 2 / 사용언어 : 파이썬(python) (0) | 2022.02.16 |
---|---|
[BOJ] 1182번 부분수열의 합 / 사용언어 : 파이썬(python) (0) | 2022.02.15 |
[BOJ] 1715번 카드 정렬하기 / 사용언어 : 파이썬(python) (0) | 2022.02.13 |
[BOJ] 11779번 최소비용 구하기 2 / 사용언어 : 파이썬(python) (0) | 2022.02.12 |
[BOJ] 2075번 N번째 큰 수 / 사용언어 : 파이썬(python) (0) | 2022.02.10 |
댓글