글 읽기 - DFS(Stack) 알고리즘 : 왜 시간초과가 날까요?

rakyu888 4년 전 0

조금이라도 시간초과가 우려되는 부분이 있다면 가감없이 지적해주시면 감사하겠습니다.

class Main{
    static boolean[][] map;
	static boolean[] visit;
	
	public static void initArray(boolean[][] arr) {
		for(int i=0; i<arr.length; i++) {
			Arrays.fill(arr[i], false);
		}
	}
	
	public static void initArray(boolean[] arr) {
		Arrays.fill(arr, false);
	}
	
	public static void addEdge(int idx1, int idx2) {
		if(!map[idx2][idx1]) {
			map[idx2][idx1] = true;
		}
	}
	
	public static ArrayList<Integer> getTargetComputer(){
		ArrayList<Integer> maxList = new ArrayList<>();
		int temp = 0;
		
		for(int i=1; i<map.length; i++) {
			initArray(visit);
			int numOfTrust = myDFS(i);
			if(numOfTrust > temp) {
				maxList.clear();
				maxList.add(i);
				temp = numOfTrust;
			}else if(temp == numOfTrust) {
				maxList.add(i);
			}
		}
		
		Collections.sort(maxList);
		
		return maxList;
	}
	
	public static int myDFS(int idx){
		Stack<Integer> s = new Stack<>();
		int count = 0;
		s.add(idx);
		visit[idx] = true;
		
		while(!s.isEmpty()) {
			int num = s.pop();
			
			for(int i=1; i<map.length; i++) {
				if(map[num][i] && !visit[i]) {
					s.add(i);
					visit[i] = true;
					count++;
				}
			}
		}
		
		return count;
	}
	
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String[] info = br.readLine().split(" ");
			int numOfRelation = Integer.parseInt(info[1]);
			int size = Integer.parseInt(info[0]);
			
			map = new boolean[size+1][size+1];
			visit = new boolean[size+1];
			
			initArray(map);
			
			for(int i=0; i<numOfRelation; i++) {
				String[] line = br.readLine().split(" ");
				addEdge(Integer.parseInt(line[0]), Integer.parseInt(line[1]));
			}
			
			Iterator<Integer> it = getTargetComputer().iterator();
			while(it.hasNext()) {
				System.out.print(it.next() + " ");
			}
			
		}catch(Exception e) {
			e.printStackTrace();
		}
	}
}

djm03178 4년 전 2

존재하는 간선 정보만 가지고 돌려도 O(N(N+M))인데, 이 코드는 인접 리스트가 아닌 인접 행렬을 가지고 있어 DFS 한 번 당 존재하지 않는 간선을 포함하여 O(N^2)개의 간선을 확인하기 때문에 O(N^3)이 됩니다.

rakyu888 4년 전 0

말씀해주신 코멘트를 참고해서 인접 행렬을 인접 리스트로 바꿔서 DFS 한 번 당 존재하는 간선들만 확인하도록 바꿔봤습니다.

역시 시간초과가 나긴 하는데 language를 java -> java11 로 바꿔서 채점하니까 Pass가 뜨네요. 허허.. 이건 무슨 경우인지.

아래 코드의 경우, 존재하는 간선 정보만 가지고 돌렸으므로 O(N) * O(N+M) 이 되는게 맞나요? ( myDFS() 부분 빅오 계산이 틀린 듯 합니다만.. ) getTargetComputer() myDFS()

class Main{
    static ArrayList<ArrayList<Integer>> list;
	static boolean[] visit;
	
	public static void initArray(boolean[][] arr) {
		for(int i=0; i<arr.length; i++) {
			Arrays.fill(arr[i], false);
		}
	}
	
	public static void initArray(boolean[] arr) {
		Arrays.fill(arr, false);
	}
	
	public static void addEdge(int idx1, int idx2) {
		if(!list.get(idx2).contains(idx1)) {
			list.get(idx2).add(idx1);
		}
	}
	
	public static ArrayList<Integer> getTargetComputer(){
		ArrayList<Integer> maxList = new ArrayList<>();
		int temp = 0;
		
		for(int i=1; i<list.size(); i++) {
			initArray(visit);
			int numOfTrust = myDFS(i);
			if(numOfTrust > temp) {
				maxList.clear();
				maxList.add(i);
				temp = numOfTrust;
			}else if(temp == numOfTrust) {
				maxList.add(i);
			}
		}
		
		Collections.sort(maxList);
		
		return maxList;
	}
	
	public static int myDFS(int idx){
		Stack<Integer> s = new Stack<>();
		int count = 0;
		s.add(idx);
		visit[idx] = true;
		
		while(!s.isEmpty()) {
			int nowIdx = s.pop();
			Iterator<Integer> it = list.get(nowIdx).iterator();
			while(it.hasNext()) {
				int newIdx = it.next();
				if(!visit[newIdx]) {
					s.add(newIdx);
					visit[newIdx] = true;
					count++;
				}
			}
		}
		
		return count;
	}
	
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String[] info = br.readLine().split(" ");
			int numOfRelation = Integer.parseInt(info[1]);
			int size = Integer.parseInt(info[0]);
			
			list = new ArrayList<>();
			visit = new boolean[size+1];
			
			for(int i=0; i<=size; i++) {
				list.add(new ArrayList<>());
			}
			
			for(int i=0; i<numOfRelation; i++) {
				String[] line = br.readLine().split(" ");
				addEdge(Integer.parseInt(line[0]), Integer.parseInt(line[1]));
			}
			
			Iterator<Integer> it = getTargetComputer().iterator();
			while(it.hasNext()) {
				System.out.print(it.next() + " ");
			}
			
		}catch(Exception e) {
			e.printStackTrace();
		}
	}
}

djm03178 4년 전 0

언어 버전이 달라지면 내부 구현도 달라지니까 시간 차이는 충분히 발생할 수 있습니다.

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

문제

문제

출처

ICPC

DFS(Stack) 알고리즘 : 왜 시간초과가 날까요?

rakyu888 4년 전 0

djm03178 4년 전 2

rakyu888 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말