[Programmers] 부대복귀

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

BFS로 간단하게 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 roads 벡터를 토대로 양방향 그래프를 만들어 줍니다.

2. sources 벡터를 순회하면서 destination으로부터 source로 갔을 때 최소 경로를 BFS 알고리즘을 통해 구해줍니다.

2.1 이때 도달할 수 없을 경우 answer에 -1을 추가하고 도달할 수 있을 경우 answer에 최단시간을 추가해 줍니다.

3. 2번을 통해 구한 answer를 반환해 줍니다.

 

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <queue>
	using namespace std;
	const int MAX = 1e5 + 1;
	vector<int> graph[MAX];
	vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
	for (vector<int> road : roads)
	{
	graph[road[0]].push_back(road[1]);
	graph[road[1]].push_back(road[0]);
	}
	vector<int> answer;
	for (int source : sources)
	{
	if (source == destination)
	{
	answer.push_back(0);
	continue;
	}
	bool canReach = false;
	bool visited[MAX] = {false,};
	queue<pair<int, int>> q;
	q.push({destination, 0});
	visited[destination] = true;
	while (!q.empty())
	{
	int cur = q.front().first;
	int dist = q.front().second;
	q.pop();
	if (cur == source)
	{
	answer.push_back(dist);
	canReach = true;
	break;
	}
	for (int next : graph[cur])
	{
	if (visited[next])
	{
	continue;
	}
	visited[next] = true;
	q.push({next, dist + 1});
	}
	}
	if (!canReach)
	{
	answer.push_back(-1);
	}
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~