[Java] 백준 ABCDE

문제

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

13023번: ABCDE

알아야 할 개념

• dfs 백트래킹

코드

dfs 탐색시 주의점을 알려준 문제

예제에 사이클 그래프가 보여서 난이도가 높은줄 알고 당황했었다. 해당 문제는 모든 정점에서 dfs 를 돌리는것으로 간단히 풀이 가능하다.

 

풀이는 다음과 같다.

1. 주어진 그래프를 무방향 인접 그래프로 구현한다. 
2. 모든 정점에대해 DFS 탐색을 한다. 
3. DFS 탐색 깊이가 4 ( 시작 = 0 ) 이상이면 탐색을 종료하고 1 리턴한다.
4. 그렇지 않으면 0 리턴한다.

백트래킹을 연습하는 문제라고 생각한다.

플래그를 세워서 dfs 탐색 종료 안하면 항상 모든 것을 탐색함으로 주의할것

풀이

자바

package solve;

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

public class Main {
    List<List<Integer>> g;
    boolean flag ;
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        System.out.println(m.solve());
    }
    public int solve()throws IOException{
        //입력을 받는다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        g =  new ArrayList<>();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());//친구 개수
        for(int i=0 ;i < n; i++){
            g.add(new ArrayList<>());
        }
        for(int i =0 ;i < m ;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            g.get(a).add(b);
            g.get(b).add(a);
        }
        boolean[] v = new boolean[n];
        for(int i =0 ;i < n ;i++){
            v[i] = true;
            flag = false;
            if(dfs(v, 0, n, i) == 1) return 1;
            v[i] = false;
        }
        return 0;
    }
    public int dfs(boolean[] v, int level, int n, int cur){
        if(flag || level >= 4){
            flag = true;
            return 1;
        }
        for(int nv : g.get(cur)){
            if(!v[nv]){
                v[nv] = true;
                dfs(v, level+1, n, nv);
                v[nv] = false;
            }
        }
        return flag ? 1 : 0;
    }
}