글 읽기 - 시간초과 질문 있습니다.... 고수님들 알려주세요ㅠㅠ

mesahwi 5년 전 0

나름 최적화했다고 생각하는데 시간 초과가 나오네요

제 풀이 방법은 :

방문한 노드를 black에, 방문 중인 노드를 gray에 넣으며 dfs하는 것입니다.

gray에 있는 노드를 다시 방문했을 경우 그 index를 이용해 cycle되는 노드의 수를 계산했습니다.

부탁드립니다ㅜㅜ 도와주세요

import java.util.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i = 0;i<t;i++) {
			int n = sc.nextInt();
			Graph graph = new Graph(n);
			for(int j = 0;j<n;j++) {
				graph.edge(j+1, sc.nextInt());
			}
			graph.cycle2();
			System.out.println(n-graph.cnt);
		}
		sc.close();
	}
}
class Graph{  
	int v;
	List<LinkedList<Integer>> list = new ArrayList<>();
	List<Integer> black = new LinkedList<>();  //visited
	List<Integer> gray = new LinkedList<>();  //visiting
	int cnt;
	
	Graph(int v){
		this.v = v+1;
		for(int i = 0;i<this.v;i++){
			list.add(new LinkedList<>());
		}
		
	}
	void edge(int from, int to) {
		list.get(from).add(to);
	}
	

	void cycle2() {
		for(int i = 1;i<this.v;i++) {
			if(!black.contains(i)) {
				cycle2(i);
				gray = new LinkedList<>();
			}
		}
	}
	void cal(int c) {
		this.cnt += gray.size() - gray.indexOf(c);
	}
	void cycle2(int c) {
		if(gray.contains(c)) {
			cal(c);
		}else {
			gray.add(c);
			int tmp = list.get(c).get(0);
			if(!black.contains(tmp)) {
				cycle2(tmp);
			}
		}
		if(!black.contains(c))
			black.add(c);
	}
	
}

atomzeno 5년 전 1

코드를 안 읽긴 했지만 아마 n²인 거 같네용(모든 정점에서 dfs를 돌리면 안됨...check를 해서 방문한 정점은 다시 방문하지 않게 해야함)

제 생각으로는

7
3 1 3 7 3 4 6

를 예로 들면

1로 탐색을 했을때, 1-3-3이 cycle이 되니까, 1-X, 3-O로 표시하고

2로 탐색을 했을때, 1은 방문한 적이 있으므로 X

3은 O

4는 4-7-6-4 cycle이므오 4,6,7에 O를 표시

5는 5-3탐색에서 3은 방문한 적이 있으므로 X

이렇게 짜면 O(n)될듯한데....

mesahwi 5년 전 0

답변 감사합니다ㅎㅎㅎ

그런데 38~45줄의 cycle2()에서

전에 들린 점들은 제외한다는 걸 구현했는데(정확히는 40줄)

그렇게 하는게 아닌가요?

atomzeno 5년 전 1

.contains 함수의 시간복잡도가 O(1) 맞죠?

djm03178 5년 전 1

단순 링크드 리스트이기 때문에 contains는 평균적으로 리스트를 반 돌아야 됩니다. O(N)입니다.

atomzeno 5년 전 1

.contains 말고 배열 쓰세용...

mesahwi 5년 전 0

하하 감사합니다

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

문제

문제

출처

ICPC

시간초과 질문 있습니다.... 고수님들 알려주세요ㅠㅠ

mesahwi 5년 전 0

atomzeno 5년 전 1

mesahwi 5년 전 0

atomzeno 5년 전 1

djm03178 5년 전 1

atomzeno 5년 전 1

mesahwi 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말