[Java] 백준 세 친구

1. 문제분석

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

17089번: 세 친구

1부터 N까지의 사람이 주어지고 각 친구관계를 보여준다.

이 사람들 중 3명을 뽑았을 때 각 친구수가 가장 적은 사람수를 구하면 된다.

즉, 1 2 3 4의 친구관계가 주어지면 1 2 3 4 중 3명을 뽑았을 때 그 친구수가 가장 작은 값을 출력하면 된다.

2. 시행착오

먼저 문제가 이해안갔다. 친구관계를 주는데 무슨 또 친구를 뽑으라는건지..

일단 N명 중 3명을 뽑는 것으로 이해했다. 그래서 생각한 방법은 조합으로 해볼려고했다.

 

1. 조합

1 2 3 4 중 3명을 뽑는다. 단, 순서에 상관없이 뽑는다. (1 2 3과 3 2 1은 같은 친구를 뽑는 것이니 패스한다.)

그리고 친구인지 아닌지 검증한다. 친구면 값을 계산후 최솟값을 구한다.

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

public class Solution {

    static int size, answer;
    static int[][] map;
    static int[] friends;

    public static void main(String[] args) throws IOException {
        // N 명중 3사람, ABC를 고른다, 세사람은 모두 친구여야 한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        size = Integer.parseInt(st.nextToken());
        int inputSize = Integer.parseInt(st.nextToken());

        friends = new int[size + 1];
        map = new int[size + 1][size + 1];

        for (int i = 0; i < inputSize; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            friends[a]++;
            friends[b]++;

            map[a][b] = 1;
            map[b][a] = 1;
        }
        answer = Integer.MAX_VALUE;
        comb( new boolean[size + 1], 3, 0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }


    static void comb(boolean[] visited, int r, int start){
        if(r == 0){
            int[] output = new int[3];
            int cnt = 0;
            for(int i = 1; i<=size; i++) {
                if(visited[i]){
                    output[cnt++] = i;
                }
            }
            int result = check(output);
            if(result != -1) answer = Math.min(result, answer);
            return;
        }
        for(int i = start; i<=size; i++){
            visited[i] = true;
            comb(visited,r -1 ,i+1);
            visited[i] = false;
        }
    }

    static int check(int[] arr){
        //친구인지 검증
        if(map[arr[0]][arr[1]] == 0 || map[arr[0]][arr[2]] == 0  || map[arr[1]][arr[2]] == 0) return -1;
        return friends[arr[0]] + friends[arr[1]] + friends[arr[2]] - 6;
    }
}

조합으로 구하고 3개를 뽑은 뒤 check로 검증했다.

시간초과가 나왔다. 결과는 잘 나오긴 한다.

사람수가 최대 4천명이다. 재귀로 돌리면 상당히 많은 시간이 나오기때문에 안된다.

 

2. 단순 3중 for문

간단하게 생각해보니 3명이면 3번 반복하면 되는 것 아닌가?

또, 전체 탐색할 필요없이 아니면 바로 continue를 하는 것이다.

이렇게 하니 답이 나왔다. 이제 코드를 보자

3. 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        // N 명중 3사람, ABC를 고른다, 세사람은 모두 친구여야 한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int size = Integer.parseInt(st.nextToken());
        int inputSize = Integer.parseInt(st.nextToken());

        int[] friends = new int[size + 1];
        int[][] map = new int[size + 1][size + 1];

        for (int i = 0; i < inputSize; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            friends[a]++;
            friends[b]++;

            map[a][b] = 1;
            map[b][a] = 1;
        }
        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= size; i++) {
            for (int j = 1; j <= size; j++) {
                if (i == j || map[i][j] != 1) continue;
                for (int k = 1; k <= size; k++) {
                    if (i == k || j == k || map[i][k] != 1 || map[j][k] != 1) continue;
                    int value = 0;
                    value += friends[i] - 2;
                    value += friends[j] - 2;
                    value += friends[k] - 2;

                    answer = Math.min(value, answer);
                }
            }
        }
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }
}

3중 for문으로 구현했다. i와 j를 비교하고 k와 i, j를 비교했다.

마지막에 2를 빼준 이유는 처음에 값을 넣어줄 때 양방향으로 구현했기 때문이다.(친구 1,2 == 친구 2,1)

4. 마무리

문제가 정말 이해안됐다. 뭐를 해야하는지.. 문제만 이해했다면 쉽게 해결할 수 있는 문제다.