최근 풀이 241031

-> 전략 안세우고 그냥 dfs로 진입했따가 메모리 초과됨.
--> 전략을 잘 세우자.

• 실패한 코드
  https://www.acmicpc.net/submit/18352/85848898

• 성공한 코드
  https://www.acmicpc.net/submit/18352/85857281

풀이전략

1) 문제를 읽어보면, 동일한 가중치라는 것을 판단할 수 있다.
2) 최소값 테이블을 만들어서 확인하는 구조를 이룸.

--> 결론 : 동일한 가중치에 인접한 노드를 사용하므로, bfs로
접근하자!

코드

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

// 18352. 특정 거리의 도시 찾기 
// 23:11 ~ 

int main() 
{
	int n, m ,k , x;
	cin >> n >> m >> k >> x;

	// [1] {2,3};
	// x로부터 시작해서 진행하는 것이므로
	
	// 동일한 가중치 이므로 -> bfs 
	// 큐에다가 넣고 진행하는데 .
	// 방문 체크를 인접한 부분에서 먼저 처리를 해야 함.

	// 정점 개수
	vector<vector<int>>v(n + 1);

	// 다리 몇개 연결할 건지
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
	}

	//for (int i = 1; i < v.size(); ++i)
	//{
	//	int ssize = v[i].size();
	//
	//	cout << i << "인덱스의 원소들은 " << endl;
	//	for (int j = 0; j < ssize; ++j)
	//	{
	//		cout << v[i][j] << endl;
	//	}
	//	
	//}

	vector<int>res;
	vector<bool>check(n + 1, false);

	queue<pair<int, int>>q;
	q.push(make_pair(x , 0));

	while (!q.empty())
	{
		int cnt = q.front().second;
		int node = q.front().first;
		q.pop();

		// 종료문.

		if (check[node] == true)
		{
			//cout << "2" << endl;
			continue;
		}

		check[node] = true;
		if (k == cnt)
		{
			res.push_back(node);
		}

		// 연결된 노드가 없으면 중단하자.
		if (v[node].size() == 0)
		{
			//cout << "1" << endl;
			continue;
		}

		
		// 4번에 연결된 정점이 없는 것을 조건 처리해야 함.	

		for (int i = 0; i < v[node].size(); ++i)
		{	
			q.push(make_pair(v[node][i] , cnt + 1));
		}

	}


	//cout << "result " << endl;

	sort(res.begin(), res.end());
	for (auto iter : res)
	{
		cout << iter << endl;
	}

	if (res.size() == 0)
		cout << -1;

}