Python3
문제
https://www.acmicpc.net/problem/5014
키워드
- 그래프 탐색
- 너비 우선 탐색
문제 풀이
문제 요구사항
- 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다.
- 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.
- 엘리베이터의 U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)
강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램
만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력
변수 및 함수 설명
- f: 건물의 총 층수
- s: 강호가 위치한 층
- g: 스타트링크가 위치한 층
- u: 위로 가는 층수
- d: 아래로 가는 층수
(1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000)
- queue: bfs 탐색을 위해 필요한 큐
- visited: 방문 처리 리스트
- loc: 현재 위치
- nloc: 다음으로 이동할 위치
- bfs(): bfs를 구현하는 함수
풀이
(입력 및 선언)
- f, s, g, u, d를 입력받는다
- 큐와 방문 처리 리스트를 선언한다.
(강호가 위치한 층부터 시작)
- 큐에 강호가 위치한 층(s)를 넣고, 해당 층을 방문 처리한다.
(이때 방문처리를 하지 않으면 틀린 답이 나올 수 있다.) - bfs함수를 호출한다.
(bfs 함수)
- 큐에 원소가 있을 때까지 반복한다.
- 현재 위치를 loc 변수에 저장한다.
- 만약 현재 위치가 스타트링크가 위치한 층(g)이라면 현재 방문 리스트 값 - 1을 반환한다.
(위치해 있던 층도 카운트했기 때문) - 현재 위치에서 올라갈 수 있는 만큼과 내려갈 수 있는 만큼 반복한다.
- 만약 다음 이동할 층이 0보다 크고 f보다 작거나 같으며 (문제에서 건물은 1층~f층까지 있다고 제시), 방문하지 않은 곳이라면 방문 처리를 하고 큐에 다음 층을 넣는다.
- 큐를 다 돌 때까지 반환되지 않았으면 엘리베이터를 이용해 g층에 갈 수 없기 때문에 use the stairs를 반환한다.
최종 코드
from collections import deque
f, s, g, u, d = map(int, input().split())
queue = deque([])
visited = [0 for _ in range(f+1)]
def bfs():
while queue:
loc = queue.popleft()
if loc == g:
return visited[loc] - 1
for nloc in (loc + u, loc - d):
if 0 < nloc <= f and not visited[nloc]:
visited[nloc] = visited[loc] + 1
queue.append(nloc)
return 'use the stairs'
queue.append(s)
visited[s] = 1
print(bfs())피드백
보자마자 어떤 알고리즘을 써야 하는지, 어떤 부분에서 그래프적으로 풀 수 있을지 고민이 되었다. 1697번 숨바꼭질과 문제가 흡사하다.
I mean