반응형
알고리즘 분류 : BFS
엘리베이터를 이용하여 S 층부터 G 층까지 가는 최단 거리를 구하는 문제다. 이동은 U 버튼, D 버튼을 통해서만 가능하다.
- 처음 층은 S 층부터 시작한다.
- 현재 층을 X 층이라 하면, 다음 층은 X+U 층이거나, X-D 층이다.
- 다음 층이 1 층에서 F 층 사이인지 확인한다.
- 존재하는 층이거나 아직 방문하지 않은 층이라면 이동한다.
- G 층에 도착할 때까지 BFS 탐색을 진행하고, 도착하면 버튼 누른 횟수를 출력한다.
- 도착하지 못하면, "use the stairs"를 출력한다.
C++ 소스코드
#include <cstdio> #include <cstring> #include <queue> using namespace std; int F, S, G, U, D; int dist[1000001]; void bfs() { queue<int> q; q.push(S); dist[S] = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (x == G) { printf("%d\n", dist[x]); return; } for (int nx : {x+U, x-D}) { if (nx < 1 || nx > F || dist[nx] >= 0) continue; q.push(nx); dist[nx] = dist[x]+1; } } printf("use the stairs\n"); } int main() { scanf("%d %d %d %d %d", &F, &S, &G, &U, &D); memset(dist, -1, sizeof(dist)); bfs(); return 0; }
Python 3 소스코드
from collections import deque def bfs(): q = deque() q.append(S) dist[S] = 0 while q: x = q.popleft() if x == G: print(dist[x]) return for nx in (x+U), (x-D): if 1 <= nx <= F and dist[nx] == -1: q.append(nx) dist[nx] = dist[x]+1 print("use the stairs") F, S, G, U, D = map(int, input().split()) dist = [-1]*(F+1) bfs()
참고
- 백준 온라인 저지 : BOJ 5014
반응형