[백준] 13023 ABCDE - DFS(깊이우선탐색) + 브루트포스(bruteforce) JAVA

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

13023번: ABCDE

코드설명

DFS(깊이우선탐색) + 브루트포스(bruteforce) 문제입니다.

문제에서 주어진 

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

이 관계를 정의해보면, 즉 5명이 연속으로 친구인지 확인하는 문제입니다.

그렇기에 DFS로 깊이우선탐색하며 5명이지만 관계는 4번이므로 4번 탐색을 완료하면 성공한 사례입니다.

 

모든 관계를 확인하기 위해 0번 사람, 1번 사람, 2번 사람... 각각 의 사람별로 시작점을 모두 진행해줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, M, T;
    public static int[] alphabet;
    public static int answer = 0;
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    public static boolean[] visited;
    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());
        visited= new boolean[N];
        
        for(int i=0;i<N;i++) {
        	graph.add(new ArrayList<Integer>());
        }
        for(int i=0;i<M;i++) {
        	st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	graph.get(a).add(b);
        	graph.get(b).add(a);
        }
        
        for(int i=0;i<N;i++) {
        	visited= new boolean[N];
        	visited[i] = true;
        	simulate(0, i);
        	if(answer == 1)
        		break ;
        }
        System.out.println(answer);
        
    }
    
    public static void simulate(int level, int idx) {
    	if(level == 4) {
    		answer = 1;
    		return ;
    	}
    	for(int i=0;i<graph.get(idx).size();i++) {
    		int friend = graph.get(idx).get(i);
    		if(visited[friend] == false) {
    			visited[friend] = true;
    			simulate(level + 1, friend);
    			visited[friend] = false;
    		}
    	}
    	
    }

}