[백준] 13023 ABCDE - JAVA

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

13023번: ABCDE

 

⏰ 친구관계를 행렬로 구현했더니 시간초과가 났다. > 인접리스트로 

 

 

알고리즘

• 최소 4개의 친구관계(A→B→C→D→E)가 연결되어 있는지 확인하기 위해 깊이우선탐색인 DFS로 구현 
• 백트래킹
• 주어진 친구관계는 인접리스트로 구현 ( 인접행렬시 시간초과 ) 
• 사람의 수가 5명보다 많더라도, 만족하는 친구관계는 주어진 4개만 만족하면 된다. (=DFS에서 탐색 깊이가 4이상이면 친구 관계 존재) 

---

 

구현 과정

• ArrayList<List<Integer>> list : 주어진 친구관계를 저장하기 위한 인접리스트 
• checked[] : DFS 탐색에서 각 사람이 현재 탐색중인 친구 관계에 포함되어있는지 확인하기 위한 boolean 형 배열
• dfs(int i, int cnt) : i와 친구인 다음 사람으로 깊이우선탐색, 몇번 째 친구 관계 탐색인지 확인하기 위한 cnt 변수 

 

1. 주어진 M개의 친구관계를 인접리스트에 양방향으로 저장한다. (0 1 이라면 0의 친구 1 = 1의 친구 0)

 

2. N명의 사람에 대해 DFS 탐색을 반복한다. (0 ≤ i < N) 인 i부터 시작하여 DFS 탐색을 시작했을 때 친구 관계가 존재하는지 확인  

 

3. DFS , 깊이우선탐색 과정은 다음과 같다. 매개변수 ▶  i: i의 친구 찾는 중, cnt : 몇번 째 연결된 관계인지

• 종료조건 : cnt 가 4라면 result 를 1로 하여 리턴한다.
  A→B→C→D→E 의 친구관계를 만족하려면 탐색 관계가 4번 이루어져야 한다. cnt 가 4라는 것은 4명 이상이 연결되어 있다는 뜻 (= 친구 관계 존재) 
• i의 친구 중, 아직 친구 관계에 포함되지 않은 (checked가 false) 친구를 찾아 checked, dfs 
• 백트래킹 구현을 위해 아래에 'checked = false' 코드를 추가한다. (return시, false) 

 

 

4. 만약 result가 1이 되었을 경우 2번 과정의 반복을 종료한다. 

 

5. 최종적으로 result를 출력. 

 

---

 

소스 코드

import java.util.*;
import java.io.*;
	
public class Main {
	static boolean checked[] ; 
	static ArrayList<List<Integer>> list = new ArrayList<>() ; 
	static int N; 
	static int result; //결과: 친구관계 존재 1, 존재x 0
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		st= new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); //사람의 수 
		for(int i=0; i<N; i++) list.add(new ArrayList<>()); 
        
		int M = Integer.parseInt(st.nextToken()); //관계의 수 
		while(M-- >0) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		for(int i=0; i<N; i++) {			
			checked= new boolean[N]; 
			checked[i] = true; 
			dfs(i,0); //i를 처음 시작점으로 두어 친구관계 성립하는지 확인 
			
			//존재하면 더이상 탐색할 필요 x
			if(result == 1) break; 

		}
		
		System.out.println(result);
	}//end of main 
	
	private static void dfs(int i, int cnt) {		
		if(cnt == 4) {
			result = 1;
			return; 
		}
		
		for(int j : list.get(i)) {
			if(!checked[j]) {
				checked[j] = true; 
				dfs(j, cnt+1);
				checked[j] = false; //백트래킹
			}
		}
	}
}//end of class