[백준] 13023 ABCDE - DFS, 시간초과 JAVA

https://www.acmicpc.net/problem/13023

13023번: ABCDE

 

문제풀이

일반적인 DFS문제인데, 문제이해가 조금 헷갈린 문제입니다.

문제에서 A,B,C,D,E 가 존재하는지 확인하는데 이떄 고정적으로 DFS를 통해서 무조건 4번 깊이의 DFS가 가능한지 확인하는 문제입니다.

 

코드

 

처음에 틀렸던 부분은

//    	if(visited[start] == false) {
..........
//		}

이 부분입니다. .

이 부분같은경우, 제 생각에 기존에 방문했었던 위치의 visited[start]가 무조건 false 일경우에만(한번도 가지 않았을경우에만) 처리했었는데, 이렇게 할경우, 나 같은경우 visited[end]도 체크하므로 미리 visited[start]를 false로 바꿔놓는데 그 이후의 값이 무조건 visited[start]값이 visited[end] 이므로 값이 들어가지 못하는 점을 놓쳤었습니다.

 

또 이문제같은경우 계속해서 시간초과가 납니다.

public static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();

위 형태의 인접리스트 안에 인접리스트를 사용하는 방식을 사용하였는데, 

계속해서 시간초과가 났습니다.

 

아래의 2개 코드 모두 시간초과가 나는 상황인데

그리하여 인접리스트를 배열형태로 만들어서 사용하려했는데 똑같이 시간초과가 나는 상황입니다.

public static ArrayList<Integer>[] arr;

 

 

이중 인접리스트를 활용한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	public static int N, M, A, B;
	public static boolean[] visited; 
	public static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
	public static int result = 0;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	for(int i=0;i<N;i++) {
    		arr.add(new ArrayList<>());
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		A = Integer.parseInt(st.nextToken());
    		B = Integer.parseInt(st.nextToken());
    		arr.get(A).add(B);
    		arr.get(B).add(A);
    	}
    	
    	for(int i=0;i<N;i++) {
    		visited = new boolean[N];
    		dfs(i, 0);
    	}
    	System.out.println(result);
    } 
    
    public static void dfs(int start, int cnt) {
    	if(cnt == 4) {
    		result = 1;
    		return ;
    	}
//    	if(visited[start] == false) {
    		visited[start] = true;
    		for(int i=0;i<arr.get(start).size();i++) {
    			int end = arr.get(start).get(i);
    			if(visited[end] == false) {
        			visited[end] = true;
        			dfs(end, cnt + 1);
        			visited[end] = false;    				
    			}
    		}
//		}
	}
    
}

 

 

 

인접리스트를 배열형태로 사용한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	public static int N, M, A, B;
	public static boolean[] visited; 
	public static ArrayList<Integer>[] arr;
	public static int result = 0;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new ArrayList[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = new ArrayList<>();
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		A = Integer.parseInt(st.nextToken());
    		B = Integer.parseInt(st.nextToken());
    		arr[A].add(B);
    		arr[B].add(A);
    	}
    	
    	for(int i=0;i<N;i++) {
    		visited = new boolean[N];
    		dfs(i, 0);
    	}
    	System.out.println(result);
    } 
    
    public static void dfs(int start, int cnt) {
    	if(cnt == 4) {
    		result = 1;
    		return ;
    	}
		visited[start] = true;
		for(int i=0;i<arr[start].size();i++) {
			int end = arr[start].get(i);
			if(visited[end] == false) {
    			visited[end] = true;
    			dfs(end, cnt + 1);
    			visited[end] = false;    				
			}
		}
	}
}