[백준] 18352 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

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

문제를 읽자마자 bfs 로 풀어야됨을 알고 문제를 바로 풀었다. 하지만 메모리 초과가 계속 나서 배열의 크기를 봤는데 vector로 선언하여 문제 없었다... 

 

그래서 오랜 고민 끝에 중복되는 연산이 있는지 확인하였다. 문제는 했던 연산을 반복하여 연산의 횟수가 늘어나기 떄문이였다. 도시가 도로를 통해 이동할 때 현재 이동한 거리보다 짧은 거리가 다음 이동할 도시에 저장되어 있으면 queue 에 저장할 필요가 없다. 왜냐하면 초반에 모든 배열을 1e9로 선언하였기 때문에 만약에 거리가 짧다면 이미 전에 이동한 도시임을 뜻하며 이미 큐에 저장되어 있을 것임을 뜻한다. 즉, 큐에 한 번더 저장하면 이전에 했던 연산을 다시 하는 것이다. 다시 하면 중복 연산이 됨으로 메모리 초과가 일어난다! 이를 if 문을 통하여 queue에 넣을지 말지 판단하였다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9

using namespace std;

vector<int> arr[300001];
int dist[300001];
int N, M, K, X;

void bfs()
{
	queue<int> q;
	q.push(X);

	while (!q.empty())
	{
		int start = q.front();
		q.pop();

		if (arr[start].empty() || dist[start] >= K)
			continue;

		for (int i = 0; i < arr[start].size(); i++)
		{
			int num = arr[start][i];
			if (dist[num] > dist[start] + 1)
			{
				q.push(num);
				dist[num] = dist[start] + 1;
			}
			
		}
	}
}

int main()
{
	
	cin >> N >> M >> K >> X;
	
	
	for (int i = 1; i <= N; i++)
	{
		dist[i] = INF;
		
	}
	dist[X] = 0;

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a].push_back(b);
	}

	bfs();

	vector<int> ans;
	for (int i = 1; i <= N; i++)
	{
		if (dist[i] == K)
			ans.push_back(i);
	}

	if (ans.empty())
	{
		cout << -1;
	}
	else
	{
		for (int i = 0; i < ans.size(); i++)
		{
			cout << ans[i] << "\n";
		}
	}

	
}

 

문제를 빨리 구현하였지만, 시간 초과 때문에 시간이 오래 걸렸다. 다음에 bfs, dfs를 만나면 중복되는 연산이 있음을 먼저 확인하는 습관을 들여야겠다.