[백준] 17089 세 친구 - Brute Force / Java

• 문제 링크

17089번: 세 친구

 

• 풀이 과정

각각의 인원을 노드로 정의하고 각 노드간 무향 그래프 정보를 boolean 배열 map 에 저장하고,

각 노드의 연결 노드의 수, 즉 친구의 수를 저장할 int 배열 cnt 에

입력받은 노드를 인덱스로써 해당 위치에 +1 을 수행한다.

 

인원 중 세 사람을 선택하므로 3중 for 문으로 조합을 구할 수 있으며,

선택된 세 사람이 모두 친구일 경우, 해당 인원의 친구 수를 모두 더하고

선택된 나머지 인원은 빼야하는 조건에 의해 -2 * 3 = -6 을 수행한다.

 

해당 값과 친구 수의 최솟값 min 을 비교 및 작은 값으로 갱신하여,

min 값의 변화 여부에 따라 -1 또는 min 값을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] map = new boolean[n + 1][n + 1];
        int[] cnt = new int[n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            map[y][x] = true;
            map[x][y] = true;

            cnt[y]++;
            cnt[x]++;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (!map[i][j])
                    continue;

                for (int k = j + 1; k <= n; k++) {
                    if (!map[i][k] || !map[j][k])
                        continue;

                    min = Math.min(min, cnt[i] + cnt[j] + cnt[k] - 6);
                }
            }
        }

        bw.write((min == Integer.MAX_VALUE ? -1 : min) + "\n");
        bw.flush();
    }

}