(cpp) Baekjoon 18352번 문제 ‘특정 거리의 도시 찾기’ - 그래프 탐색, BFS, 다익스트라

07 Feb 2023 on Programming Languages

Baekjoon 18352번 문제 ‘특정 거리의 도시 찾기’ - 그래프 탐색, BFS, 다익스트라

---

문제

풀이

코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int n, m, k, x, from, to;
vector<vector<int>> g;
vector<int> check_bfs;
vector<int> result;


void bfs() {
	int start = x;
	queue<int> q;
	q.push(x); //다녀온 곳이자 새로운 시작점을 기록하는 큐.
	check_bfs[x] = 0;

	while (!q.empty()) {
		int cur = q.front(); //현재 위치는 항상 큐의 맨 앞 요소
		q.pop(); //현재 위치 기억만 해두고 큐는 비우기
		
		for (int i = 0; i < g[cur].size(); i++) {
			//현재 위치에서 갈 수 있는 지점의 수
			int next = g[cur][i]; //현재그래프에 포함된 모든 점이 next지점의 후보
			if (check_bfs[next] == -1) {
				//그치만 가본적 없는 곳이여야 함.
				check_bfs[next] = check_bfs[cur] + 1; //가서 체크하고
				q.push(next); //그 지점이 새로운 시작점이 됨
			}
			//가본적 있는 곳이면 아무 것도 하지 않고 pass
		}
	}
	for (int i = 1; i <= n; i++) {
		if (check_bfs[i] == k) {
			result.push_back(i); //최단거리 k를 갖는 도시 번호를 모두 result에 입력
		}
	}
}

int main() {
	cin >> n;
	cin >> m;
	cin >> k;
	cin >> x;
	g = vector<vector<int> >(n + 1); //크기가 n+1인 2차원 벡터 생성
	check_bfs= vector<int>(n + 1, -1); //원소가 n+1개이고 각 원소는 -1로 초기화
	for (int i = 0; i < m; i++) {
		cin >> from >> to;
		g[from].push_back(to);
	}

	bfs();
	if (result.size() == 0) {
		cout << -1; //result에 아무것도 없으면 -1출력
	}
	else 
	{
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << '\n'; //result에 담겨있는 도시 번호들 출력
		}
	}	
}