[Java] 백준 13023번 : ABCDE 풀이

✅문제

 

✅문제 풀이 

관계가 A-B, B-C, C-D, D-E가 있는지 확인하는 문제이다.

모두다 한번씩 확인하려면 for문이 5번 돌아가기 때문에 A-B, C-D를 모두 한번씩 돌려서 for문을 2번만 사용하고

B-C, D-E가 있는지 한번씩만 확인하면 효율적으로 문제를 풀 수 있다.

밑에 풀이는 Pair, Graph 클래스를 사용하여 문제를 풀었다.

Lombok... 있다없으니까 소중함을 다시 느낍니다... ㅠㅠ

✅Code

public class Beak13023 {
    public static class Pair{
        private int x;
        private int y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int getX() {
            return x;
        }
        public int getY(){
            return y;
        }
    }
    
    public static class Graph {
        private List<List<Integer>> arrays;
        private List<Pair> edges;
        private int size;

        public Graph(int size) {
            arrays = new ArrayList<>();
            edges = new ArrayList<>();
            this.size = size;

            for (int i = 0; i < size; i++) {
                List<Integer> row = new ArrayList<>();
                for (int j = 0; j < size; j++) {
                    row.add(0);
                }
                arrays.add(row);
            }
        }

        public void addEdge(int i, int j) {
            arrays.get(i).set(j, 1);
            arrays.get(j).set(i, 1);
            edges.add(new Pair(i,j));
        }
        public boolean check(int i, int j){
            return arrays.get(i).get(j) == 1;
        }
        public List<List<Integer>> getArrays() {
            return arrays;
        }
    }

    public static class GraphService {
        private Graph graph;

        public GraphService(Graph graph) {
            this.graph = graph;
        }

        private boolean check() {
            List<List<Integer>> arrays = graph.getArrays();

            for (Pair firstPair : graph.edges) {
                for (Pair secondPair : graph.edges) {
                    int a = firstPair.getX();
                    int b = firstPair.getY();
                    int c = secondPair.getX();
                    int d = secondPair.getY();

                    if (a == b || a == c || a == d || b == c || b == d || c == d)
                        continue;

                    if (!graph.check(b,c))
                        continue;

                    List<Integer> filteredArrays = new ArrayList<>();

                    for (int i = 0; i < arrays.get(d).size(); i ++){
                        if(arrays.get(d).get(i) == 1)
                            filteredArrays.add(i);
                    }

                    for (Integer e : filteredArrays) {
                        if (a == e || b == e || c == e || d == e)
                            continue;

                        return true;
                    }

                }
            }
            return false;
        }
    }

    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());

        Graph graph = new Graph(n);

        for (int i = 0; i < m ; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(
                    Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken())
            );
        }

        GraphService graphService = new GraphService(graph);

        if (graphService.check()) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }
    }
}