백준 (BOJ) 13023 ABCDE java dfs

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

13023번: ABCDE

 

 

 

비방문처리 시점을 찾는 게 중요했던 dfs 문제

 

시간 초과가 나지 않게끔 연결돼 있는 노드들만 따로 hashset에 저장해서 반복문을 돌렸다.

 

아 참고로, 연속된 노드 5개가 연결된 경로 4개가 존재하면 되는 문제이다.

 

1 - 2 - 3 - 4 - 5 답

1 - 2 - 3 - 4 - 1 답

1 - 2 - 3 - 4 오답

 

(문제가 논란의 소지가 다분히 있는 거 같은데... ABCDE인데 ABCDA가 가능하면 안 되는 거 아닌가?)

 

비방문 처리 시점은 아래의 경우를 생각해보면 된다.

 

1 - 3 - 4   (4와 연결된 노드가 더 없어서 실패가 판명났다.)

 

근데 1 - 5 - 3 - 7 - 9 라는 성공할 수 있는 경우가 있다.

 

위에서 3을 방문해버렸기 때문에 방문할 수 없게 되면 많이 난감해진다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static boolean[] visited;
    static HashSet<Integer> linkCheck;
    static ArrayList<Integer>[] map;
    static boolean flag;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        map = new ArrayList[N];
        for(int i=0; i<N; ++i) map[i] = new ArrayList<>();

        linkCheck = new HashSet<>();

        for(int i=0; i<M; ++i){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            map[x].add(y);
            map[y].add(x);

            linkCheck.add(x);
            linkCheck.add(y);
        }

        flag = false;
        for(Integer v : linkCheck){
            visited = new boolean[N];
            visited[v] = true;
            if(dfs(0, v)){
                flag = true;
                break;
            }
        }

        if(flag) System.out.print(1);
        else System.out.print(0);

    }

    static boolean dfs(int depth, int v){
        if(4 <= depth){
            return true;
        }

        // v에 연결된 노드들 탐색
        for(Integer a : map[v]){
            if(!visited[a]){
                visited[a] = true;
                if(dfs(depth+1, a)) return true;
                visited[a] = false; // 재방문할 수 있게 3을 unvisited 처리 ex) 1 - 3 - 4 (실패) --> 1 - 3 - 5 - 6 - 7 (성공)
            }
        }

        return false;
    }

}