[BOJ/JAVA] 13023번: ABCDE

13023번: ABCDE

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

키워드

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.

• B는 C와 친구다.

• C는 D와 친구다.

• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성

---

구현

• 한 노드에서 다른 노드로의 최대 거리를 구하는 문제이다.

• 깊이 우선 탐색을 이용하여 구현한다.

• 최대 거리가 4 이상이면 위와 같은 친구관계가 존재하는 것이고 그렇지 않으면 존재하지 않는다.

---

코드

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

public class java_13023 {

    // 인접 행렬
    static List<List<Integer>> adj;
    // 노드의 수, 간선의 수
    static int N, M;

    // 최대 거리
    static int maxDegree;

    // 중복 방문처리
    static boolean[] isVisited;

    // 깊이 우선 탐색
    static void dfs(int index, int degree) {
        // 거리가 4라면
        // A-B-C-D-E 형태가 만들어진다. -> 종료
        if (degree == 4) {
            maxDegree = 4;
            return;
        }

        List<Integer> thisNode = adj.get(index);

        for (int nextNode : thisNode) {
            if (!isVisited[nextNode]) {
                isVisited[nextNode] = true;
                dfs(nextNode, degree + 1);
                // 다른 방향으로 가면 최대가 될 수 있으므로 false처리 후 추후 재방문
                isVisited[nextNode] = false;
            }
        }

    }

    // A-B-C-D-E 형태의 친구 관계가 존재하는지 판단하는 메소드
    static boolean solution() {
        // 모든 노드를 돌면서 최대 거리가 4 이상이 되는지 체크
        for (int i = 0; i < N; i++) {
            isVisited = new boolean[N];
            isVisited[i] = true;
            dfs(i, 0);

            // 길이가 4 이상인가?
            if (4 <= maxDegree) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // degree 가 4인 친구관계가 존재하는가?
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 노드 삽입
        adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>());
        }

        // 간선 삽입
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            adj.get(from).add(to);
            adj.get(to).add(from);
        }

        boolean result = solution();

        if (result) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

        br.close();
    }
}

---

Uploaded by N2T