[백준][13023번] ABCDE

문제 URL

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

전체 풀이 (비트마스크) *

이 문제는 그래프 개념을 활용하여 풀 수 있다. 즉, 사람은 정점 간선은 친구관계를 나타내면된다. A, B, C, D, E 정점이 있을때 (1) A,B와 C,D는 간선리스트를 활용하여 구한다. (2) B와 C가 친구관계인지는 인접행렬을 활용한다. (3) D가 E가 존재하는지는 인접리스트를 활용한다.

자세한 것은 주석참조

import java.util.*;
class Edge {
    int from, to;
    Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }
}

public class Main{
    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 = (ArrayList<Integer>[]) 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;
        for  (int i=0; i<m; i++) {
            for (int j=0; j<m; j++) {
                int A = edges.get(i).from;
                int B = edges.get(i).to;
                int C = edges.get(j).from;
                int D = edges.get(j).to;
                //A,B,C,D 모두 달라야한다.
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    continue;
                }
                //B와 C가 친구관계여야한다.
                if (!a[B][C]) continue;
                //D와 인접한 정점이 있는지 간선리스트를 활용한다.
                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);
    }
}