백준 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명의 학생들을 결정하시오.

 

유형 : 백트랙캥

 

접근 방식

• 처음에 문제를 보고 (친구의 친구는 내 친구)인줄 알고 union-find 문제인 줄 알았다. 하지만 다시 읽어보면 모두 서로 친구 사이라는 문구에서 알수 있듯 그냥 다 서로 친구여야 하는 것이다.
• 백트랙킹에서 가장 중요한 것은 가지치기이다. 어떤 조건에서 탐색을 멈춰야 할지 혹은 아예 탐색을 하지 않아야 하는지 판단하는 것이 중요하다.

탐색을 해야 하는 경우

• count[] 배열을 한개 만들고 들어오는 입력에 대하여 친구의 수를 1씩 증가하여 카운트한다. (초깃값 1 : 나는 나의 친구 ~~!)
• count 배열의 값이 k 이상인 경우에만 백트랙킹을 수행한다.

백트랙킹

• 문제의 출력 조건을 읽어보면 결국 단 1개의 경우만 구하면 된다.
• 1개의 경우의 숫자들은 작은 수로만 이루어져 있도록 설계되어 있기 때문에 1개의 친구 관계를 출력한 경우 더이상 탐색을 멈추도록 한다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int k = 0;

    static int[][] graph;

    static ArrayList<Integer> peek = new ArrayList<>();

    static boolean[] v;
    static int[] count;

    static boolean find = false;

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

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

        graph = new int[n+1][n+1];
        v= new boolean[n+1];
        count = new int[n+1];

        for(int i=1;i<=n;i++){
            count[i] = 1;
        }


        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x][y] = 1;
            graph[y][x] = 1;

            count[x] += 1;
            count[y] += 1;
        }

        for(int i=1;i<=n;i++){

            if(count[i] >= k){
                peek.add(i);
                v[i] = true;
                travel(i,1);
                peek.remove(peek.indexOf(i));
                v[i] = false;

                if(find){break;}
            }
        }

        if(!find){
            System.out.println(-1);
        }
        br.close();
    }

    static void travel(int cur,int count){
        if(find){
            return;
        }

        if(count == k){
            StringBuilder sb = new StringBuilder();

            for(int next: peek){
                sb.append(next+"\n");
            }

            find = true;
            System.out.print(sb);
            return;
        }

        for(int i=cur+1;i<=n;i++){
            if(graph[cur][i] == 1 && !v[i]){
                boolean keep = true;

                for(int next : peek){
                    if(graph[i][next] == 0){
                        keep = false;
                        break;
                    }
                }

                if(keep){
                    v[i] = true;
                    peek.add(i);
                    travel(i,count + 1);
                    peek.remove(peek.indexOf(i));
                    v[i] = false;
                }
            }
        }
    }
}