백준 18352 [C++]

www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

 

1. 풀이방법

 

- 일단 N의 개수가 300,000이므로 굉장히 큽니다.

 

- 이차원배열을 고정으로 선언할 경우 작동이 안됩니다.

 

- 따라서 vector를 이용하여 vector[x].push_back(y) --> x에서가는 y에대해 가는 간선이 있다는 정보저장

 

- 조건 중 중요한것은 간선의 가중치가 모두 1이라는 것....!  --->이게 있으므로 bfs를 수행하여 최단거리를 구할 수 있다  고 생각 할 수 있습니다.

 

- 최단거리로 가는 도시들만 출력해야 하므로 visited 배열을 통해 방문한 노드인지 체크를 하며 bfs를 수행하면 됩니다.

 

- 큐를 이용했고 거리만큼의 bfs를 수행한 후에는 벡터에 옴겨 sorting을 해서 차례로 출력하여 주었습니다.

 

 

 

2. 주의사항

 

- 조건상에서 왜 bfs를 수행해서 구할 수 있는지 파악 (정당성)

 

 

3. 나의 코드

 

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

queue<int> tmpqueue;
vector<int> edge[300001]; //간선정보저장
bool visited[300001]; //방문정보 저장
int N, M, K, X;
int loadlength;

void inputedge() { //간선정보를 저장
	int x, y;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		edge[x].push_back(y);
	}
}

void resultoutput() { //오름차순 정렬 (큐에서 벡터로 옴겨서)
	vector<int> resultsave;
	while (tmpqueue.empty()!=true) {
		resultsave.push_back(tmpqueue.front());
		tmpqueue.pop();
	}
	sort(resultsave.begin(), resultsave.end());
	for (int i = 0; i < resultsave.size(); i++) {
		cout << resultsave[i] << "\n";
	}
}

void bfs(int X) {
	tmpqueue.push(X);
	visited[X] = true;
	while (1) {
		if (tmpqueue.empty()) { cout << -1 << "\n"; break; }
		if (loadlength == K) { resultoutput(); break; }
		int qsize = tmpqueue.size();
		while(qsize--){
			int startnode = tmpqueue.front();
			for (int i = 0; i < edge[startnode].size(); i++) {
				if (visited[edge[startnode][i]] == false) {
					tmpqueue.push(edge[startnode][i]);
					visited[edge[startnode][i]] = true;
				}
			}
			tmpqueue.pop();
		}
		loadlength++;
	}
}

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

	cin >> N >> M >> K >> X;
	inputedge();
	bfs(X);

	return 0;
}