[백준] 17089번 세 친구 - Java

문제 링크

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

문제

N명의 사람이 있고, 여기서 세 사람 A, B, C를 고르려고 한다. 세 사람은 모두 친구여야 한다.

세 사람을 고르는 방법은 매우 많이 있을 수 있다. 이때, A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때, 세 사람은 빼고 계산해야 한다. 즉, A의 친구 수를 계산할 때, B와 C는 빼고 계산해야 하고, B의 친구 수를 계산할 때는 A와 C, C의 친구 수를 계산할 때는 A와 B를 빼고 계산해야 한다.

입력

첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친구라는 것을 의미한다.

사람은 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 A의 친구 수 + B의 친구 수 + C의 친구 수의 최솟값을 출력한다. 만약, 문제 조건대로 세 사람을 고를 수 없는 경우에는 -1을 출력한다.

알고리즘: 브루트포스, 그래프 이론

풀이

3명을 고르는 모든 경우의 수를 구한다. 그리고 그 3명 모두가 친구라면 친구 수의 합을 구해서 그 중 최솟값을 구한다.

시간 복잡도는 그래프를 인접 리스트로 표현한 DFS이기 때문에 N+E (E는 간선)이고, 총 N번 반복하기 때문에 O(N(N+E))라고 할 수 있다. -> (오름차순으로 탐색하기 때문에 실제로는 E보다 작음)

소스 코드

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

public class Main {
    static int N,M;
    static ArrayList<ArrayList<Integer>> graph_list = new ArrayList<>();
    static Stack<Integer> result = new Stack<>();
    static ArrayList<Integer> ans = new ArrayList<>();
    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());
      for(int i=0; i<=N; i++) graph_list.add(new ArrayList<>());
      for(int i=0; i<M; i++) {
          StringTokenizer n_st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(n_st.nextToken());
          int b = Integer.parseInt(n_st.nextToken());
          graph_list.get(a).add(b);
          graph_list.get(b).add(a);
      }
      DFS();
      if(ans.size()==0) System.out.println(-1);
      else {
          System.out.println(Collections.min(ans));
      }
    }
    
    static void DFS() {
        if(result.size()==3) {
            if(graph_list.get(result.get(0)).contains(result.get(2))) {
                // A,C가 친구라면 A, B, C 모두 친구
                ans.add(graph_list.get(result.get(0)).size() + graph_list.get(result.get(1)).size() + graph_list.get(result.get(2)).size()-6);
            }
            return;
        }
        if(result.size()==0) {
            for(int i=1; i<=N; i++) {
                result.push(i);
                DFS();
                result.pop();
            }
        } else {
            int top = result.peek();
            for(int i=0; i<graph_list.get(top).size(); i++) {
                int n = graph_list.get(top).get(i);
                if(top<n) {
                    result.push(n);
                    DFS();
                    result.pop();
                }
            }
        }
    }
}