[백준] 5014번 - 스타트링크

☞ 이번 문제는 풀면서 정말 많은 방법들을 갖고 접근해보았다. 

처음에는 재귀를 이용해 풀려고 했는데, 재귀를 끝내기 위한 조건을 찾는 와중에 어떻게 하면 Up and Down을 계속 지속하며 뺑뺑 도는 부분은 나올 수 있을지에 대한 부분에서 막혔었다.

 그래서 다른 방법을 찾아 보았고, 대부분 어떤 점에서 다른 점까지의 거리를 구하는 문제에 사용되는 너비우선탐색(BFS)법을 사용해보았다. 

 

● BFS로 풀기 위해 해당 건물을 인접리스트의 형태로 표현 해보았다.

int tmp[2] = { U, -(D) };
	for (int i = 1; i <= F; i++) {
		for (int j = 0; j < 2; ++j) {
			if (j == 0) {
				if (i + tmp[j] <= F) {
					adj[i].push_back(i+tmp[j]);
				}
			}
			else {
				if (i + tmp[j] > 0) {
					adj[i].push_back(i+tmp[j]);
				}
			}
		}
	}

 

이 인접리스트를 이용해 기본 bfs 알고리즘을 통해 S에서 다른 점으로의 dist를 구해 dist[G]값을 구하면 끝!

 

● 전체코드 

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

int F, S, G, U, D;
vector<vector<int>> adj;
vector<int> dist;


void bfs(int start) {
	dist = vector<int>(F + 1, -1);
	queue<int> q;
	dist[start] = 0;
	q.push(start);
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i];
		
			if (dist[there] == -1) {
				q.push(there);
				dist[there] = dist[here] + 1;

			}
		}
	}
}

int main() {
	cin >> F >> S >> G >> U >> D;
	adj = vector<vector<int>>(F+1);
	int tmp[2] = { U, -(D) };
	for (int i = 1; i <= F; i++) {
		for (int j = 0; j < 2; ++j) {
			if (j == 0) {
				if (i + tmp[j] <= F) {
					adj[i].push_back(i+tmp[j]);
				}
			}
			else {
				if (i + tmp[j] > 0) {
					adj[i].push_back(i+tmp[j]);
				}
			}
		}
	}

	bfs(S);
	if (dist[G] == -1) {
		cout << "use the stairs";
	}else
	cout << dist[G];
}

소스 코드 : https://github.com/withseungryu/Algorithms

withseungryu/Algorithms

궁금하신 것이 있으시다면 댓글로 남겨주세요!~