[DFS] 백준 13023번

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

[조건]
첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

[출력]
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

 

문제분석

DFS 문제풀이
1. 시간복잡도 : O (노드수 + 간선수) 
  - 계산 : 노드 수 최대 2000 , 간선 수 최대 2000 = 시간복잡도 (4000 * 2000) 모든 노드를 진행할 때
2. A -> B -> C ->D -> E 의 관계를 확인하려면 5명의 대한 이어져있는 관계도이니, DFS 진행도 5번 이상 진행되면 된다
3. 5번 이상이 한번이라도 나오면 즉시 종료 ( 1 출력 )

 

• 관계도 (첫번째 예시)

0 -> [4]
1  -> [7]
2  -> [7]
3  -> [7, 4, 5]
4  -> [7, 3, 6, 0]
5  -> [3]
6  -> [4]
7  -> [1, 3, 4, 2]

슈도코드

N (노드 저장)
M (관계 저장)
checkArr 배열 생성 (방문 확인)
relationMap (친구관계 확인)

relationMap, checkArr 초기화

for( 관계 수만큼 반복 ){
    relationMap 관계초기화;
}

for( 노드 수만큼 반복 ){
    dfs();
    if (5번 이상이면){
        return;
    }
}

if( arrive ) {
    1 출력
}
0출력

 

 

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;


public class App {

    private static boolean arrive = false;    

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int humanSize = Integer.parseInt(st.nextToken());
        int relationSize = Integer.parseInt(st.nextToken());
        boolean[] checkArr = new boolean[humanSize];

        HashMap<Integer, List<Integer> > map = new HashMap<>();
        
        for (int i =0; i< humanSize; i++){
            map.put(i, new ArrayList<>());
            checkArr[i] = false;
        }

        for(int i =0; i< relationSize; i++){
            st = new StringTokenizer(bf.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            
            /* 친구관계는 양방향 */
            List list = map.get(B);
            list.add(A);
            
            list = map.get(A);
            list.add(B);
        }
        
        for (int i =0 ; i< humanSize; i++){
            dfs(map, i, checkArr, 1); 
            if (arrive){
                break;
            }
        }

        if(arrive){
            System.out.println("1");
        }else{
            System.out.println("0");
        }
        

    }

    private static void dfs(HashMap<Integer, List<Integer>> map, int index, boolean[] checkArr, int depth){
        if (depth ==5 ||arrive){
            arrive =true;
            return;
        }

        checkArr[index] = true;
        for(int i : map.get(index)){
            if ( checkArr[i] == false) {
                dfs(map, i, checkArr, depth+1);
            }
        }

        checkArr[index] = false; // 복구하는 메커니즘 (다른쪽 방향을 선택하므로)
    
    }

   
}