글 읽기 - 이 문제 어떻게 접근해야하는지 힌트주시면 안될까요?

jumpingz 6년 전 0

해당문제를 1 번에서 각 정점들로 갈 수 있는지 여부를 확인하고 2번부터 N번까지 각 정점에서 N번으로 갈 수 있는지를

BFS 를 통해서 저장하고 테스트가 주어질떄마다 인덱스 정보를 보고 결과를 출력하는 방식을 선택했는데요

아무래도 정점개수와 간선개수가 어마무시하다보니 어떠한 입력을 사용해도 계속 시간초과가 발생하네요..

아래 주석친 영역을 수정해야 할 듯한데 다른 방법은 생각이 안나네요...

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#pragma warning(disable:4996)
vector< vector<int> > v(100001);
bool Check[100001], StartInfo[100001], ViaInfo[100001];

void BFS(int start);
bool Via(int start, int end);

int main()
{
	int a, b, N, M, K;
	scanf("%d%d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
	}


	/*StartInfo[1] = true;	ViaInfo[N] = true;

	BFS(1);	
	for (int i = 2; i <= N; i++)
	{
		memset(Check, false, sizeof(Check));
		if (Via(i, N) == true)
			ViaInfo[i] = true;
	}*/

	scanf("%d", &K);

	for (int i = 0; i < K; i++)
	{
		scanf("%d", &a);

		if (StartInfo[a] == false)
			printf("Destroyed the CTP\n");
		else
		{
			if(ViaInfo[a] == false)
				printf("Destroyed the CTP\n");
			else
				printf("Defend the CTP\n");
		}
	}

	return 0;
}

void BFS(int start)
{
	queue<int> q;
	q.push(start);
	Check[start] = true;

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

		for (int next : v[temp])
		{
			if (Check[next] == false)
			{
				q.push(next);
				Check[next] = true;
				StartInfo[next] = true;
			}
		}
	}
}

bool Via(int start, int end)
{
	queue<int> q;
	q.push(start);
	Check[start] = true;

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

		for (int next : v[temp])
		{
			if (next == end)
				return true;

			if (Check[next] == false)
			{
				q.push(next);
				Check[next] = true;
				StartInfo[next] = true;
			}
		}
	}

	return false;
}

jh05013 6년 전 1

BFS를 "뒤집어서" 실행하면 각 정점에서 v로 갈 수 있는지를 볼 수 있습니다.

jumpingz 6년 전 0

머리가 멍청해서.. 계속 고민해봐도 어떻게 해야할지 모르겟네용... 어떤 의미인지 좀 더 자세하게 설명해주실수있으신지요 ㅠ

jh05013 6년 전 0

a에서 b로 가는 경로를 거꾸로 따라가면 b에서 a로 가는 경로가 됩니다. 즉 각 정점에서 N번으로 가는 경로가 있다면 거꾸로 갔을 때 N번에서 각 정점으로 가는 경로가 됩니다.

이제 문제는 거꾸로 된 경로를 찾는 것인데, 모든 간선을 뒤집으면 경로의 방향도 뒤집을 수 있습니다.

jumpingz 6년 전 0

아 그렇군요 정말 감사합니당

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

문제

문제

출처

ICPC

이 문제 어떻게 접근해야하는지 힌트주시면 안될까요?

jumpingz 6년 전 0

jh05013 6년 전 1

jumpingz 6년 전 0

jh05013 6년 전 0

jumpingz 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말