[백준13023] ABCDE - 그래프 표현 연습

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

13023번: ABCDE

 

위 문제를 푸는 방법은 여러가지지만,

인접행렬, 인접 리스트, 간선 리스트를 모두 사용해보기 위한 방법으로 풀어본다.

 

 

문제 풀이

1. 간선 리스트를 통해 A, B, C, D를 특정한다.

2. 인접 행렬을 통해 B, C가 친구인지 알아낸다.

(인접 행렬이 인접리스트보다 뛰어난 유일한 경우는 두 정점 사이에 간선이 있는지 없는 지 구하는 경우.)

3. 인접 리스트를 통해 D의 친구인 E 가 있는 지 탐색

4. A, B, C, D, E 중 동일인이 없다면 1을 출력

 

package graph;

import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Scanner;

class Edge {
    int from = 0;
    int to = 0;

    public Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }
}
public class Baekjoon13023 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        //인접행렬
        boolean[][] a = new boolean[n][n];
        //인접리스트
        ArrayList<Integer>[] g = new ArrayList[n];
        //간선리스트
        ArrayList<Edge> edges = new ArrayList<Edge>();

        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            edges.add(new Edge(from, to));
            edges.add(new Edge(to, from));
            a[from][to] = a[to][from] = true;
            g[from].add(to);
            g[to].add(from);
        }

        //친구 관계는 양방향이니 간선의 총 개수는 m*2
        m *= 2;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if(i == j) continue;

                int A = edges.get(i).from;
                int B = edges.get(i).to;
                int C = edges.get(j).from;
                int D = edges.get(j).to;

                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    continue;
                }

                //B -> C
                if (!a[B][C]) {
                    continue;
                }

                //D -> E
                for (int E : g[D]) {
                    if (A == E || B == E || C == E || D == E) {
                        continue;
                    }
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        System.out.println(0);
    }
}