[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