[C++] BOJ(백준) 5014 스타트링크

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

BFS 문제다.

BFS에 익숙한 편은 아니라서 정보 없이 문제를 접했다면 BFS를 떠올리지 못했을 것 같다.

(BFS 문제임을 알고도 BFS보다 노가다로 구현하려고 했으니까...)

2차원 배열이 아니라는 점도 BFS로 떠올리지 못한 이유 같다.

 

1차원 배열에서는 앞뒤로 움직이는 두 가지 경우만 고려해주면 된다.

배열에 대한 정보가 입력되는 것이 아니기 때문에 board 배열은 사용하지 않았다.

visit 배열로 해당 층을 방문했는지 여부만 확인했다.

 

#include <iostream>
#include <queue>
using namespace std;

int f, s, g, u, d;
int visit[1000000];

int BFS() {
	// <층 수, cnt>
	queue<pair<int, int>> q;

	// 현재 층 기록
	q.push(make_pair(s, 0));
	visit[s] = 1;

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int cur = q.front().first;
		int count = q.front().second;
		q.pop();

		int up = cur + u;
		int down = cur - d;

		// 위, 아래 층으로 갔을 때 원하는 층이면 리턴
		if (up == g || down == g) return count + 1;

		// 건물의 층을 넘지 않고 방문한 적이 없으면
		if (up <= f && !visit[up]) {
			visit[up] = 1;
			q.push(make_pair(up, count + 1));
		}
		// 1층 이상이고 방문한 적이 없으면
		if (down > 0 && !visit[down]) {
			visit[down] = 1;
			q.push(make_pair(down, count + 1));
		}
	}

	// 큐가 비어버리면 엘리베이터로 갈 수 없으므로 0 리턴
	return 0;
}

int main() {
	cin >> f >> s >> g >> u >> d;

	// 현재 층과 목적지 층이 같다면 바로 종료
	if (s == g) {
		cout << 0;
		return 0;
	}

	int cnt = BFS();
	
	if (cnt) cout << cnt;
	else cout << "use the stairs";
}

입력 값의 범위가 크다보니 메모리도 많이 사용하고 시간 소요도 좀 있는 편이다.