글 읽기 - 시간초과를 어떻게 줄일지 감이 안 옵니다 ㅠ

kim031504 4년 전 0

위상정렬을 통해

큐의 자료구조로 작업을 하였습니다.

큐가 빌 때까지 while문을 돌고, 안에서 N만큼 점검 작업이 있어서 N^2이 나오는 것 같은데,

이것 보다 더 줄일 수 있는 방법이 있을까요...?? ㅠㅠ

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

	int N, K;
	int pre[32000] = { 0, };	// 선행자의 개수
	vector<int> suc[32000];	// 후행자 목록 리스트
	bool check[32000] = { false, };	// 방문 여부 체크

	vector<int> start_node;	// 시작 노드들을 담는다.

	cin >> N >> K;

	// 연결 정보 입력
	for (int i = 0; i < K; i++)
	{
		int u, v;

		cin >> u >> v;

		suc[u - 1].push_back(v - 1);

		pre[v - 1]++;
	}


	// 정답을 줄줄이 담을 것이다.
	vector<int> result;

	queue<int> Q;

	// 선행자가 하나도 없는 첫 노드 먼저 큐에 push!
	for (int i = 0; i < N; i++)
	{
		if (pre[i] == 0)
		{
			// 첫 노드 넣어주고 반복문 탈출!
			Q.push(i);
			break;
		}
	}

	// 모든 노드를 돌아 큐가 빌 때까지!
	while (!Q.empty())
	{
		int  u = Q.front();
		Q.pop();

		// 아직 방문 안 한 노드라면
		if (!check[u])
		{
			// 결과에 순서대로 push!
			result.push_back(u);
			check[u] = true;
		}
		
		for (auto next : suc[u])
		{
			--pre[next];

			// 선행자가 이제 없다면
			if (pre[next] == 0)
			{
				// 그리고 방문을 안 했다면
				if (!check[pre[next]])
				{
					// 선행자 작업이 끝났으므로 result 뒤에 순서대로 붙는다
					result.push_back(pre[next]);
					check[pre[next]] = true;
				}
				
				// 그리고 큐에 넣어져서 해당 노드의 작업 진행!
				Q.push(next);
			}
			else // 선행자가 아직 남아 있다면
			{
				for (int i = 0; i < N; i++)
				{
					// 선행자가 없고 아직 방문 안 해준 노드 작업을 처리해준다.
					if (pre[i] == 0 && !check[i])
					{
						Q.push(i);
					}
				}
			}
		}

		// 만을 큐가 비었다면 한 그래프에 대해 이미 끝에 도달했다는 뜻이다.
		if (Q.empty())
		{
			// 만일 그래프가 여러 개라면 하나 그래프 끝나고서 다른 그래프 작업을 위함이다.
			for (int i = 0; i < N; i++)
			{
				if (pre[i] == 0 && !check[i])
				{
					Q.push(i);
				}
			}
		}
	}

	// 출력 과정!
	int len = result.size();

	for (int i = 0; i < len; i++)
	{
		cout << result[i]+1 << ' ';
	}

	cout << '\n';

	return 0;
}

wjsqjawns 4년 전 2

기존에 썼던 댓글에 첨부했던 코드가 너무 직접적이라 삭제했습니다.

대신, O(N^2)일 필요가 없는 이유를 말씀드리겠습니다.

큐에 있는 정점들은 어차피 while문을 돌 때마다 하나씩 빠져나오고, 큐에 있는 정점들은 들어오는 간선이 없다는 것, 그리고 앞서 큐에 들어온 정점들이 우선권이 있다는 것은 당연합니다.

즉, 큐에 있는 정점들은 방문 여부를 확인할 필요가 없습니다. 방문을 할 수가 없으니까요.

또한, 매 반복(while)마다 큐에 있는 정점과 연결된 정점들의 들어오는 간선 수를 줄이고, 만약 해당 정점의 들어오는 간선 수가 0개가 된다면, 이를 큐에 추가합니다.

그럼 방법은 간단합니다. 큐의 가장 앞에 있는 값을 result에 넣어주기만 하면 됩니다.

굳이 탐색을 할 필요가 없습니다.

그리고, 40번째 줄의 반복문에서, 탈출을 할 필요가 없습니다. 탈출을 하지 않으면 알아서 처음부터 들어오는 간선이 없는 정점들을 모두 큐에 넣어주는데, 탈출을 해버리면 작성자님께서 작성하신 것처럼 일일이 확인해야 합니다.

kim031504 4년 전 1

우와! 감사합니다!

불필요한 연산을 하는 코드를 지우고,

덱으로 구현하였더니 맞았습니다!

지저분하게 작성한 코드인데, 잘 분석해주셔서 감사해요~!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과를 어떻게 줄일지 감이 안 옵니다 ㅠ

kim031504 4년 전 0

wjsqjawns 4년 전 2

kim031504 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말