[BOJ] 17089번 : 세 친구 Java 풀이

노드가 최대 4000개, 간선이 최대 4000개라는 제한이 들어온다.

여기서 3개의 노드를 선택한다. 이때 이 3개의 노드는 서로 인접한 상태여야 한다. 각 노드를 A, B, C라고 할때 A, B, C가 인접한 모든 노드의 개수 - 6의 최솟값을 구하라고 한다. 이때 노드는 중복해서 세야 한다.

4000 C 3을 하기에는 제한이 조금 빡세기에 더 쉬운 방법을 생각해봐야 한다. 우선 각 노드별로 자신이 인접한 노드의 개수를 구하는 것은 어렵지 않다. 이 값을 활용해보자.

A, B, C를 동시에 선정하기에는 아무리 생각해도 너무 빡빡하니, A만 먼저 구해보자. 그러면 A와 인접한 노드들 중에 B, C가 모두 존재해야 한다. 자 그럼 B를 하나 뽑아보자. C를 선정하기 위해서는 자신과 인접하고, A와 인접한 노드이면 된다.

그래서 2차원 배열로 visited[i][j] = i와 j 노드가 인접해있는가?를 표시해보자. 이제 이 값을 이용해보면? B를 기준으로 C를 뽑았을때 A와 인접한 노드인지 O(1)에 구할 수 있다.

그러면 A를 선정하는 for문, B를 선정하는 for문, C를 선정하는 for문 3번을 돌아주면 된다. 시간복잡도가 마치 O(N^3)이 되는것 같지만 사실상 간선의 개수만큼 탐색하기 때문에 시간복잡도 O(N+M)만에 문제를 해결할 수 있다.

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

public class Main {

  private static final List<Integer>[] adj = new ArrayList[4010];
  private static final int[] cnt = new int[4010];
  private static final boolean[][] isConnected = new boolean[4010][4010];
  private static int answer = 1000000000;
  private static int N;
  private static int M;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    N = Integer.parseInt(input[0]);
    M = Integer.parseInt(input[1]);
    for (int i=0; i<=N; i++) {
      adj[i] = new ArrayList<>();
    }
    for (int i = 0; i < M; i++) {
      String[] edge = br.readLine().split(" ");
      int V = Integer.parseInt(edge[0]);
      int K = Integer.parseInt(edge[1]);
      adj[V].add(K);
      adj[K].add(V);
      cnt[V]++;
      cnt[K]++;
      isConnected[V][K] = true;
      isConnected[K][V] = true;
    }
    for (int i=1; i<=N; i++) {
      for (int j=0; j<adj[i].size(); j++) {
        int next = adj[i].get(j);
        for (int k=0; k<adj[next].size(); k++) {
          int node = adj[next].get(k);
          if (node == i) continue;
          if (isConnected[i][node]) {
            answer = Math.min(answer, cnt[i] + cnt[next] + cnt[node] - 6);
          }
        }
      }
    }
    if (answer == 1000000000) answer = -1;
    System.out.println(answer);
  }

}