[문제풀이] B13023 ABCDE

ABCDE

---

  🪅 에지리스트를 인접리스트로 구현할 수 있는가
  🪅 반복동작을 수행할때마다 전의 동작이 다음 동작에 영향을 미치지 않도록 초기화해 주었는가
  🪅 flag 변수를 용도에 맞게 사용할 수 있는가
  🪅 모든 경로 탐색에 필요한 백트래킹을 할 줄 아는가

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 백준 13023번 ABCDE
 *
 * 입력:
 * 첫째 줄에 사람의 수 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을 출력한다.
 * 
 */
public class B13023_ABCDE_이우엽 {
    static List<Integer>[] graph;
    static boolean[] isVisited;
    static int depth;
    static boolean isExist;
    public static void DFS(int node) {
        if(depth == 4) {
            isExist = true;
            return;
        }
        isVisited[node] = true;
        for(int adj : graph[node]) {
            if(isVisited[adj]) continue;
            isVisited[adj] = true;
            depth++;
            DFS(adj);
            isVisited[adj] = false; // 마킹해제, 백트래킹
            depth--; // 마킹해제에 따른 값 변경
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(token.nextToken());
        int M = Integer.parseInt(token.nextToken());
        int[][] arr2d = new int[M][2];
        graph = new ArrayList[N];
        isVisited = new boolean[N];

        // 각 배열의 요소에 ArrayList로 초기화
        for(int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }

        // 관계수 M만큼 관계 입력
        for(int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            arr2d[i][0] = Integer.parseInt(token.nextToken());
            arr2d[i][1] = Integer.parseInt(token.nextToken());
        }
//        System.out.println(Arrays.deepToString(arr2d));

        for(int i = 0; i < arr2d.length; i++) {
            int u = arr2d[i][0];
            int v = arr2d[i][1];
            graph[u].add(v);
            graph[v].add(u);
        }
        // test 출력
//        for(int i = 0; i < graph.length; i++) {
//            System.out.println(i + ": " + graph[i]);
//        }

        for(int i = 0; i < graph.length; i++) {
            depth = 0;
            isVisited = new boolean[N];
            DFS(i);
            if(isExist) {
                System.out.println("1");
                return;
            }
        }
        System.out.println("0");
    }
}

💡 문제 접근 과정
ABCDE처럼 노드 5개가 연결되어 있냐고 물어보는 문제이고,
이는 즉, 그래프의 depth가 4가 되는가로 해석할 수 있다.
에지리스트로 주어진 입력을 인접리스트로 바꿔주고,
시작점을 바꿔주면서 DFS를 돌렸다(리프노드까지 내려가는)
그래서 한번이라도 depth가 4가 되면 그 즉시 1을 출력하고 프로그램을 끝냈다.

📌 모든 노드 탐색에는 백트래킹을 하면 안되지만(중복탐색), 모든 경로 탐색에는 백트래킹이 필요하다.
=> 백트래킹을 하지 않으면 전의 방문이 다음 방문에 영향을 끼치기 때문