문제

boj18352_1 boj18352_2

다익스트라, 프림, 크루스칼을 공부하고 백준에서 관련 개념을 사용하는 문제를 쉬운 것부터 풀고 있다.

쉬운 문제라 보자마자 어떻게 해야할 지 알았다. 하나 다른 점이라면 그래프를 저장할 때 directed graph라 양방향으로 저장할 필요가 없었고 multiple edge를 가질 수 있기 때문에 그래프를 vector들의 배열로 선언해 from번째 인덱스에 to들이 벡터 안에 들어있도록(graph[from] = <to1, to2, ...>처럼) 자료구조를 정했다.

1번부터 N번까지의 도시와 == 노드 N개와
M개의 단방향 도로 == edge가 M개인 directed graph
모든 도로의 거리는 1 == 모든 edge의 weight가 1 –> BFS/DFS를 쓸 수 있다
특정한 도시 X == source
최단 거리가 K == dist[i]가 K인 i를 다 출력해라
라는 것을 빨리 캐치해 신속하고 간단하게 구현했음

#include <iostream>
#include <vector>
#include <queue> // bfs
#define MAX 300001
using namespace std;

int dist[MAX];
vector<int> graph[MAX];
bool visit[MAX];

void BFS(int src) {
	queue<int> q;
	dist[src] = 0;

	q.push(src);
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (auto it = graph[now].begin(); it < graph[now].end(); it++) {
			int next = *it;
			if (!visit[next]) {
				dist[next] = dist[now] + 1;
				visit[next] = true;
				q.push(next);
			}
		}
		visit[now] = true;
	}
}

int main() {
	int N, M, K, X, i, from, to;
	bool none = true;

	cin >> N >> M >> K >> X;

	for (i = 1; i <= M; i++) {
		cin >> from >> to;
		graph[from].push_back(to);
	}

	BFS(X);

	for (i = 1; i <= N; i++) {
		if (dist[i] == K) {
			cout << i << "\n";
			none = false;
		}
	}
	if (none) cout << -1 << endl;

	return 0;
}