[백준 5014번 / C++ / BFS] 스타트 링크

BFS 를 활용한 문제가 은근 많다. 

최근 코테에서도 BFS 를 활용해서 풀었던 기억이 난다.  DFS/BFS 를 응용한 문제를 파악하고 바로 풀수 있게끔 충분히 연습하자. 

 

#접근방법

 

이 문제의 핵심은 서두에서 언급했듯이 BFS를 활용하는 것이다.

여기서 건물의 위아래로 왔다갔다하는 것이 조금 헷갈리면 건물을 오른쪽 방향으로 누웠다고 생각해보자. 

 

그러면 크기가 f인 배열에 현재 위치 s 에서 오른쪽(up), 왼쪽(down) 으로만 갈 수 있는데 목적지 g 에 도착하면 끝난다. 

 

바로 응용해보면 현재 위치를 담은 좌표를 queue에 담고 너비 우선탐색을 하는것이다. 

즉, 왼쪽으로 갔을 때 좌표값과 오른쪽으로 갔을 때 좌표값을 queue담으면 된다. 그리고 방문처리를 해준다. 

 

여기서 중요한 문제는 

1. 왼쪽 좌표값과 오른쪽 좌표값이 배열 크기를 초과하면 안된다. 

2. 방문 처리가 되지 않았을 경우에만 queue에 담는다. 

 

1번 같은경우에는 바로 이해할 것이고 2번같은 경우에 방문처리가 되어있으면 이전에 엘레베이터를 탔을 때 이미 더 빨리 해당 층을 들렸다는 의미이기에 무시하자는 거다. 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std; 
int f, s, g, u, d; 
//f 건물 높이, s 현재위지, g 목적지 , u up , d down 
int main() {
	cin >> f >> s >> g >> u >> d; 
	queue <int> q; 
	vector <bool> visited(f + 1, false); 
	q.push(s); 
	int cnt=0; 
	visited[s] = true; 
	while (!q.empty()) {
		int n = q.size(); 
		while (n--) {
			int x = q.front(); 
			if (x == g) {
				cout << cnt;
				return 0;
			}
			q.pop();
			
			int up = u + x; 
			int down = x - d; 
			if (up <= f && !visited[up] ) {
				q.push(up);
				visited[up] = true; 
			}
			if (down >= 1 && !visited[down]) {
				q.push(down); 
				visited[down] = true; 
			}
		}
		cnt++;
	}
	cout << "use the stairs"; 
}

 

5014번: 스타트링크