글 읽기 - 시간 초과 어떻게 줄일 수 있을까요...?

kim031504 4년 전 0

루트 노드를 선택한 것과 안 한 것,

그리고

현재 정점이 얼리 어댑터라면 ,다음 것은 선택해도, 안 해도 좋다.
현재 정점이 얼리 어댑터가 아니라면, 다음 것은 선택해야 한다.

라는 조건을 이용하여 코드를 짰는데,

테스트 케이스는 통과하지만 시간초과가 납니다 ㅠ

어떻게 개선시킬 수 있을까요...?

자세한 코드 설명은 주석으로 달아놨습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;	// 정점의 개수

vector<int> vt[1000001];	// 인접 리스트

bool check[1000001] = { false, };	// 방문 여부


int DFS(int idx, bool choice)
{
	// 방문 체크!
	check[idx] = true;

	int sum = 0;

	// 자기와 연결된 정점에 대해 처리
	for (int i = 0; i < vt[idx].size(); i++)
	{
		// 연결된 정점들 중 아직 방문 안 한 것들 처리!
		if (!check[vt[idx][i]])
		{
			// 현재 정점이 얼리 어댑터이면
			if (choice)
			{
				// 다음 것은 선택해도, 안 해도 좋다
				sum += min(DFS(vt[idx][i], false), DFS(vt[idx][i], true));
			}
			else // 현재 정점이 얼리 어댑터가 아니라면
			{
				// 다음 것은 선택해야 한다.
				sum += DFS(vt[idx][i], true);
			}
		}
	}

	// 자신에 대한 탐색을 마치면 원래 상태로 되돌리기
	check[idx] = false;

	// 자기 정점에 대해 계산 처리
	if (choice)
	{
		return sum += 1;
	}
	else
	{
		return sum;
	}
}


int main()
{

	// 입력 처리!
	cin >> N;

	for (int i = 0; i < N-1; i++)
	{
		int u, v;

		cin >> u >> v;

		vt[u].push_back(v);
		vt[v].push_back(u);
	}

	// 루트 노드를 선택한 것과 안 한 것 중에서 최소 개수를 출력한다.
	cout << min(DFS(1, true), DFS(1, false)) << '\n';
	

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과 어떻게 줄일 수 있을까요...?

kim031504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말