[BOJ][Java] 백준 13023번: ABCDE

문제 설명

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

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

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

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

 

문제 풀이

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.  

라는 조건이 단순히 연결만 되어있다면 성립한다고 생각했을 때 유니온 파인드 기법으로 접근할 수 있지만 예제 입력 3번이 해결되지 않습니다.

따라서 

A - B : 1 depth

B - C : 2 depth

C - D : 3 depth

D - E : 4 depth

처럼 depth가 4 이상을 갖는 그래프를 찾는 것입니다.

 

 

풀이 코드

import java.io.*;
import java.util.*;

class Main {
    private static int N, M, ans = 0;
    private static ArrayList<ArrayList<Integer>> list;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for (int i = 0; i < N; i++) list.add(new ArrayList<>());
        visited = new boolean[N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }

        for (int i = 0; i < N; i++) {
            if(ans != 1) findDepth(i, 1);
        }

        System.out.println(ans);
    }

    private static void findDepth(int start, int depth) {
        if(depth == 5) {
            ans = 1;
            return ;
        }

        visited[start] = true;
        for(int n : list.get(start)) {
            if(visited[n]) continue;
            findDepth(n, depth+1);
        }
        visited[start] = false;
    }
}

 

<출처>

13023번: ABCDE