[코딩테스트/백준 알고리즘] 13023번 - ABCDE (자바, Java 풀이)

문제

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

13023번: ABCDE

---

문제 설명

---

문제 풀이

이 문제는 DFS를 통해 길이가 5인 경로가 존재하는지 확인하는 방법으로 해결할 수 있다.

하지만 이번 풀이는 다른 방법으로 해결해보겠다.

이 방법을 위해선 그래프를 표현하는 방법 중 인접 행렬, 인접 리스트, 간선 리스트를 모두 사용해야 한다. 

1. 간선 리스트를 사용해서 A - B 를 찾는다
2. 간선 리스트를 사용해서 C - D 를 찾는다.
3. 인접 행렬을 사용해서 B 와 C가 연결되어 있는지 확인한다.
4. 입접 리스트를 사용해서 D에서 E(A, B, C, D가 아닌 친구)가 연결되어 있는지 확인한다.

---

코드

import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N, M;
        N = sc.nextInt();
        M = sc.nextInt();
        boolean[][] arrGraph = new boolean[N][N];
        List<List<Integer>> listGraph = new ArrayList<>();
        List<int[]> edgeGraph = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            listGraph.add(new ArrayList<>());
        }
        while (M-- > 0) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            /*인접 행렬*/
            arrGraph[p1][p2] = true;
            arrGraph[p2][p1] = true;
            
            /*인접 리스트*/
            listGraph.get(p1).add(p2);
            listGraph.get(p2).add(p1);
            
            /*간선 리스트*/
            edgeGraph.add(new int[]{p1, p2});
            edgeGraph.add(new int[]{p2, p1});
        }
	/*1,2 단계*/
        for(int i = 0; i < edgeGraph.size(); i++) {
            for(int j = 0; j < edgeGraph.size(); j++) {
                int A = edgeGraph.get(i)[0];
                int B = edgeGraph.get(i)[1];
                int C = edgeGraph.get(j)[0];
                int D = edgeGraph.get(j)[1];
                if (A != C && A != D && B != C && B != D) {
                
                    /*3단계*/
                    if (arrGraph[B][C]) {
                    
                        /*4단계*/
                        for (int E : listGraph.get(D)) {
                            if (A == E || B == E || C == E || D == E) {
                                continue;
                            }
                            System.out.println(1);
                            System.exit(0);
                        }
                    }
                }
            }
        }
        System.out.println(0);
    }
}

---

총평

시간초과와 힘겨운 싸움을 한 문제다.

처음 짠 코드는 5중 for문인가 사용했던 거 같은데 당연히 시간 초과가 났다.

빠른 시일 내에 DFS로 푼 풀이를 올릴 수 있도록 노력해보겠다.