[BOJ/백준] 13023 ABCDE(JAVA)

링크

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

 

문제 요약

0번~N-1번 사람 중 아래와 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구하기

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

 

제한

• 첫째 줄에 사람의 수 N, 친구 관계의 수 M
  • 5 ≤ N ≤ 2000
  • 1 ≤ M ≤ 2000
• 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다.
  • 0 ≤ a, b ≤ N-1, a ≠ b
  • 같은 친구 관계가 두 번 이상 주어지는 경우는 X
• 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

 

풀이

경로의 특징을 저장해야하는 문제로, DFS로 문제를 풀어야 합니다.

1. 모든 정점에 대해 dfs를 수행한다.
   1. 시작점은 `cnt`(친구 수) 값이 1이다.
2. dfs는 시작 정점을 기준으로 친구 관계를 따라가며 dfs 함수를 재귀적으로 호출한다.
   1. 재귀 호출할 때 `cnt`(친구 수) 값을 1 증가시킨다.
   2. 호출하기 전, 해당 정점 방문 여부를 표시한다.(겹치지 않는 A, B, C, D, E를 찾기 위해)
   3. 재귀 호출이 끝난 시점에는 방문 여부를 다시 `false`로 표시한다.
      1. 0,1,2,3 까지 시도했는데 실패했다면 다음으로 0,1,2,4 이런 식으로 시도하기 위함이다.
3. 만약 `cnt` 값이 5가 되면, 조건에 맞는 친구 관계를 발견했음을 표시하고 탐색을 종료한다.
4. 만약 아직 원하는 친구 관계를 찾지 못했다면 다른 시작 정점을 기준으로 2 과정을 반복한다.

 

코드

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

public class Main {
    static int N, M;
    static boolean findFlag;
    static ArrayList<Integer>[] edges; 
    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());
       edges = new ArrayList[N];
       visited = new boolean[N];

       for(int i=0; i<N; i++){
           edges[i] = new ArrayList<>();
       }

       for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());

            edges[first].add(second);
            edges[second].add(first);
       }

       for(int i=0; i<N; i++){
           if(!findFlag){ // 아직 조건에 맞는 친구 관계를 찾지 못 했으면 탐색
               dfs(i,1);
           }
       }
       System.out.println(findFlag ? 1 : 0);
    }

    static void dfs(int start, int cnt) {
        if(cnt == 5){ // 조건에 맞는 친구 5명을 찾으면 끝
            findFlag = true;
            return;
        }
        visited[start] = true;
        for(int next: edges[start]){
            if(!visited[next]){
                dfs(next, cnt+1);
            }
        }
        visited[start]=false;
    }
}

 

🏷 시간 복잡도

• `N`: 정점의 수
• `M`: 간선의 수
• DFS는 각 정점을 한 번씩 방문하고, 각 간선을 한 번씩 탐색하므로 `O(N + M)`
• 최종 시간 복잡도: `O(N + M)`

🏷 실행 속도

Time: 232 ms, Memory: 21980 KB