[백준]2026: 소풍(java)

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

2026번: 소풍

문제

원장선생님께서는 1부터 N까지 번호가 붙은 N(K ≤ N ≤ 900)명의 학생들 중에서 K(1 ≤ K ≤ 62)명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 정보를 F(1 ≤ F ≤ 5,600)개를 주시며 K명을 선발하라고 부탁하였다.

고은 조교를 도와 소풍을 가게 될 K명의 학생들을 결정하시오.

입력

첫째 줄에 공백으로 분리된 세 정수 K, N, F가 주어진다. 다음 F개의 줄에는 서로 친구 관계인 두 사람의 번호가 주어진다. 친구 관계는 상호적인 관계이므로 2번 학생이 4번 학생을 좋아하면 4번 학생도 2번 학생을 좋아한다. 같은 친구 관계가 여러 번 주어지는 경우는 없다.

출력

만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 학생의 번호가 제일 작은 것을 출력한다. 첫 번째 학생의 번호가 같은 경우라면, 두 번째 학생의 번호가 작은 경우를 출력하고, 이와 같은 식으로 출력한다.

예제 입력 1 

4 6 8
1 2
1 3
1 6
2 3
2 6
3 6
4 5
5 6

예제 출력 1 

1
2
3
6

---

풀이

소풍을 갈 수 있는 조건은 2가지 입니다.

1) K명 이상 친한 친구를 갖고있는가

2) 그 친한친구끼리도 모두 친한 친구인가

 

 

우선 모든 Node가 친구가 될 수 있는 조합을 구합니다.

public static void combination(int start, int cnt, int[] arr) {
    if(cnt == K) {
        if(isCycle(arr)) {
            for(int i=0; i<arr.length; i++) {
                System.out.println(arr[i]);
            }
            System.exit(0);
        }
        return;
    }

    for(int i=start; i<=N; i++) {
        if(graph[i].size() < K-1) continue;
        arr[cnt] = i;
        combination(i+1, cnt+1, arr);
    }
}

여기서 graph[1]일때 생각을 해보겠습니다.

1- 2, 3, 6 와 연결돼있고, 그러므로 1, 2, 3, 6 즉 K=4보다 크므로 소풍을 갈 수 있는 조건중 하나를 충족하게됩니다.

만약 graph[4]는

4 - 5 이므로 4, 5 즉 K=4보다 작으므로 조건 1번을 만족하지 못해 조합에 4는 고려하지 않아도 됩니다.

if(graph[i].size() < K-1) continue;

 

조합으로 K명 이상을 뽑았다면

2번 조건인 모두 친한 친구인지 확인해줍니다.

public static boolean isCycle(int[] arr) {
    for(int i=0; i<arr.length; i++) {
        for(int j=0; j<arr.length; j++) {
            if(i==j) continue;
            if(!isFriend[arr[i]].contains(arr[j])) {
                return false;
            }
        }
    }
    return true;
}

나 자신을 제외하고 서로 친한친구로 등록돼있는지 미리 등록한 HashSet을 통해서 확인해줍니다.

 

전체 코드

package 백준;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class BJ_G3_2026_소풍 {
    static int K, N, F;
    static ArrayList<Integer>[] graph;
    static HashSet<Integer>[] isFriend;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        isFriend = new HashSet[N+1];
        for(int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
            isFriend[i] = new HashSet<>();
        }

        for(int i=0; i<F; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            graph[s].add(e);
            graph[e].add(s);
            isFriend[s].add(e);
            isFriend[e].add(s);
        }

        combination(1, 0, new int[K]);
        System.out.println("-1");
    }

    public static void combination(int start, int cnt, int[] arr) {
        if(cnt == K) {
            if(isCycle(arr)) {
                for(int i=0; i<arr.length; i++) {
                    System.out.println(arr[i]);
                }
                System.exit(0);
            }
            return;
        }

        for(int i=start; i<=N; i++) {
            if(graph[i].size() < K-1) continue;
            arr[cnt] = i;
            combination(i+1, cnt+1, arr);
        }
    }

    public static boolean isCycle(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr.length; j++) {
                if(i==j) continue;
                if(!isFriend[arr[i]].contains(arr[j])) {
                    return false;
                }
            }
        }
        return true;
    }
}