[백준 / BOJ 2026] 소풍

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개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 학생의 번호가 제일 작은 것을 출력한다. 첫 번째 학생의 번호가 같은 경우라면, 두 번째 학생의 번호가 작은 경우를 출력하고, 이와 같은 식으로 출력한다.

 

풀이

---

백트래킹 & DFS로 풀었따아.‼️

 

우선 K명을 선택해야하는데 K명이 모두 서로서로 친구여야하므로 1번부터 N번의 학생 중 친구의 수가 K-1이라면 PASS~‼️🤟

그래서 friendsNum 변수로 각 친구의 수를 저장해주었다.

 

여기서 중요한 점은 친구관계로 연결이 되는 것이 아니라 선택된 학생들이 모두 친구 관계여야한다는 것이다.

isFriend(int idx) 함수는 idx번 학생과 지금까지 선택한 학생들이 모두 친구인지 확인하는 함수이다.

 

flag 변수를 사용한 이유는!

K명을 고르는 방법이 여러개라면, 첫 번째 학생의 번호가 제일 작은 것을 출력해야하기 때문에 DFS가 성공으로 끝나면 flag를 true로 두어서 더 이상 DFS를 진행하지 않도록 빠져나올 수 있게 하기 위해서 이다.

 

 

코드

---

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


public class Main_BOJ_2026_소풍 {
    static int N, K, F;
    static int[][] friends;     // 친구 관계 저장 1: 친구, 0 : 아님
    static int[] friendsNum;    // i의 친구 수
    static boolean[] isVisited; 
    static StringBuilder sb;
    static boolean flag = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

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

        friends = new int[N+1][N+1];
        friendsNum = new int[N+1];
        isVisited = new boolean[N+1];

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

            friends[x][y] = 1;
            friends[y][x] = 1;

            friendsNum[x]++;
            friendsNum[y]++;
        }

        for(int i = 1; i <= N ;i++){
            // 친구의 수가 본인 포함 K명 이상이여야함
            // K명 미만이라면 불가능하기때문!
            if(friendsNum[i] < K-1)
                continue;
            if(flag)
                break;

            isVisited[i] = true;
            DFS(i, 1);
            isVisited[i] = false;
            
        }

        if(flag)
            System.out.print(sb);
        else
            System.out.println(-1);
    }
    private static void DFS(int idx, int cnt) {
        if(flag)
            return;

        if(cnt == K){
            for(int i = 1; i <= N ; i++){
                if(isVisited[i])
                    sb.append(i).append("\n");
            }
            flag = true;
            return;
        }

        for(int i = idx+1 ; i <= N ;i++){
            if(friends[idx][i] == 1 && isFriend(i)){
                isVisited[i] = true;
                DFS(i, cnt+1);
                isVisited[i] = false;
            }
        }
    }
    private static boolean isFriend(int idx) {
        for(int i = 1; i <= N; i++){
            if(isVisited[i] && friends[idx][i] != 1)
                return false;
        }

        return true;
    }
}