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

그래프 탐색 중 너비 우선 탐색으로 푸는 문제.

[C++] 백준 1107번 리모컨

위 리모컨 문제와 똑같은 문제였다.

예전에 푼 로직이 생각나서 바로 풀 수 있었다.

 

문제풀이

리모컨 문제와 아주 유사한 문제이다.

BFS를 하게 되는데,

현재 층에서 위, 아래 층이 유효한 층이고 방문하지 않았다면 다음 층을 큐에 넣어주면서 계속 탐사하게 구현하면 된다.

 

/*
* 백준 5014번 스타트링크
* https://www.acmicpc.net/problem/5014
* 그래프 탐색 이론 - 너비 우선 탐색
*/
#include <iostream>
#include <queue>
using namespace std;

int topFloor, startFloor, destinationFloor, upFloor, downFloor;
bool visit[1000001];
bool checkArrive;
int ans;

void bfs(int startFloor) {
	queue<pair<int, int>> q;
	q.push({ 0, startFloor });
	visit[startFloor] = true;

	while (!q.empty()) {
		int curFloor = q.front().second;
		int moveCnt = q.front().first;
		q.pop();

		if (curFloor == destinationFloor) {
			checkArrive = true;
			ans = moveCnt;
			return;
		}

		int goUpFloor = curFloor + upFloor;
		if (goUpFloor <= topFloor && !visit[goUpFloor]) {
			q.push({ moveCnt + 1, goUpFloor });
			visit[goUpFloor] = true;
		}
		
		int goDownFloor = curFloor - downFloor;
		if (goDownFloor >= 1 && !visit[goDownFloor]) {
			q.push({ moveCnt + 1, goDownFloor });
			visit[goDownFloor] = true;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> topFloor >> startFloor >> destinationFloor >> upFloor >> downFloor;

	bfs(startFloor);

	if (checkArrive) {
		cout << ans;
	}
	else {
		cout << "use the stairs";
	}

	return 0;
}

코드 전문.

코드가 길지 않아서 한 번에 설명하겠다.

 

사용한 STL과 변수

• queue STL : BFS를 돌 때 사용할 큐 자료구조를 위해 include 했다.
• topFloor, startFloor, destinationFloor, upFloor, downFloor : 입력받는 F, S, G, U, D 변수
• visit 배열 : 해당 층을 방문했는지 여부를 저장하는 배열
• checkArrive : 목표하는 층에 갔는지 저장하는 변수. false일 경우 도달하지 못했음을 의미한다.
• ans : 몇 번 버튼을 눌렀는지 출력하는 결과값.

 

메인함수는 다음과 같은 순서로 이루어진다.

1. F, S, G, U, D를 입력받는다.
2. S층 부터 bfs를 시작한다.
3. checkArrive == true, 즉 목표하는 층에 간 경우에는 ans를 출력한다.
4. 아니라면, 목표하는 층에 못 간 경우 "use the stairs"를 출력한다.

 

bfs메서드는 매개변수로 시작하는 층을 입력받게 된다.

큐를 선언하게 되는데, pair형 큐이다. first에는 현재 층까지 버튼을 몇 번 눌러서 도착했는지, second에는 현재 몇 층인지를 저장하게 된다.

처음 큐에 { 0, 첫번째 층 }을 push한다.

 

그러고 난 후에 다음과 같은 로직이 큐가 비지 않을 때 까지 반복된다.

1. curFloor 변수, moveCnt 변수에 큐의 맨 앞에 있는 원소의 정보를 담고 큐를 pop()한다.
2. 만일 현재 층을 나타내는 curFloor변수가 목표하는 층이라면 checkArrive변수를 true로 바꾸고 ans에 현재 몇 번의 버튼을 눌렀는지 나타내는 moveCnt 변수의 값을 넣고 bfs 메서드를 종료시킨다.
3. 아니라면 U층 위, D층 아래 층이 유효한 층이고 방문한 적이 없는 층이라면 큐에 넣고 해당 층을 방문처리 해준다.

 

처음에 메모리 초과가 났다. 방문 처리를 반복문의 맨 처음 부분에서 해 줘서 그렇다.

BFS에서는 해당 정점을 큐에 넣을 때 방문 처리를 해줘야 한다.

 

GitHub - kimyunseok/cpp: my study-record

코드는 위에서 확인 가능하다.