글 읽기 - 다음과 같은 방법으로는 풀수 없는 문제인가요???

ohtuna 4년 전 0

84%에서 계속 시간 초과가 나서 질문드립니다.

일단 알고리즘 설명부터 하겠습니다

자기 자신 방문시 사이클 노드이므로 방문했다고 표시하고 넘어갑니다.
만약 그렇지 않은 노드의 경우 go 함수를 통하여 탐색을 시작 합니다.
탐색 과정은 방문한 노드는 체크하면서 만약 사이클 노드라면 ffind 상태 변수에 true를 주어 return 될때 원복을 하지 않습니다.
만약 사이클 노드가 아닌경우라면 원복을 합니다

혹시 이방법으로는 풀수 없는 문제 인가요? 시간복잡도는 n이지 않나요 ???

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

using namespace std;

int visit[100001];
bool ffind;


void go(int idx, vector<int> &v, int start)
{
	//시작 정점이 이미 방문한 노드면 return
	if (visit[start] == 1) return;
	//방문했던 정점이면 return;
	if (visit[v[idx]] == 1) return;
	//탐색 중 시작 노드와 마지막 방문 노드 같을 시 사이클 노드임.
	if (start == v[idx])
	{
		ffind = true;
		visit[start] = 1;
		return;
	}

	if (visit[v[idx]] == 0)
	{
		ffind = false;
		visit[v[idx]] = 1;
		go(v[idx], v, start);
		if (ffind == false)
		{
			visit[v[idx]] = 0;
		}

	}
		

}

int main()
{
	int tc;

	cin >> tc;

	while (tc--)
	{

		int n;
		cin >> n;
		vector<int>v(n);

		//정점 삽입
		for (int i = 0; i < n; i++)
		{
			cin >> v[i];
			v[i] -= 1;
		}

		for (int i = 0; i < v.size(); i++)
		{
			//방문한 정점이면 continue
			if (visit[i] == 1) continue;
			//자기 자신이면 방문 표시 하고 continue;
			if (i == v[i])
			{
				visit[i] = 1;
				continue;				
			}
			//정점 탐색
			go(i, v, i);
		}
		
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			//사이클인 노드 개수 체크
			if (visit[i] == 1)
			{
				cnt++;
			}
		}

		//전체에서 사이클 정점 빼주면 됨
		cout << v.size() - cnt << "\n";

		for (int i = 0; i < n; i++)
		{
			visit[i] = 0;
		}

	}
}

nahwasa 4년 전 0

예를들어 2 3 4 5 4 6

이럴 경우, 위 경우로는

1->2->3->4->5->4

2->3->4->5->4

3->4->5->4

4->5->4 루프 찾음!

6->6 루프 찾음!

이렇게 됩니다.

루프 찾을때 까지 동일한 동작을 계속하니 O(N^2)이 될듯하네요.

O(N)으로 되시려면

처음에 첫번째 인자에서 go함수들어갔을 때 1->2->3->4->5->4 이후로 바로 다 넘기고 6->6 으로 가야겠죠!

ohtuna 4년 전 0

@nahwasa

visit 방문으로 표시하고, 방문된 노드에 한해서는 return 하는데 그렇게 된다는건가요??

nahwasa 4년 전 0

아..? 죄송합니다.

go 함수 재귀호출에서 start가 변경되지 않길래 그렇게 판단했네요 ㅠㅠ

바로 다음으로 넘어가는거라면

저랑 같은 방식에 전 특히나 느린 자바인데.. 이게 왜 시간초과일까요 ㄷㄷ

다시 봐보겟습니다! 성급하게 댓글달아 죄송합니다.

ohtuna 4년 전 1

@nahwasa

아하 말씀하신게 무슨말인지 알겠어요 ㅋㅋ 제가 잘못이해한거 같네요 감사합니다.

nahwasa 4년 전 0

33번줄에서 다시 바꾸는군요! 그럼 처음 말한게 맞았군요!

는.. 이해하신듯하군요.

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

문제

문제

출처

ICPC

다음과 같은 방법으로는 풀수 없는 문제인가요???

ohtuna 4년 전 0

nahwasa 4년 전 0

ohtuna 4년 전 0

nahwasa 4년 전 0

ohtuna 4년 전 1

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말