BOJ - 소풍 2026번 (JAVA)

❓ 문제 - 백준 소풍 2026번 - JAVA 풀이법

 

출처 

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

2026번: 소풍

 

 

📝 문제해결법

1. 문제

• N명중에 K명을 소풍을 보내려고 선택해야한다.
• 하지만 K명 모두 친구관계이어야 하며, 만약 K명 이상인 친구관계가 존재하지 않으면 -1을 여러 개라면 번호가 작은 순서대로 K개까지만 출력해야 한다.

 

2. 해결 방법

• 우선 인접행렬로 서로의 친구관계를 표시하고, 백트래킹을 통해 조건에 맞는 경우를 구해서 k명을 선발할 수 있을지 따져본다.
• 하지만 단순 백트래킹으로 풀면 시간초과가 발생한다.
• 따라서 백트래킹을 처음 들어가는 main 부분에서 각 사람마다 친구의 명수를 배열에 저장한 뒤, 해당 사람의 친구가 만약 k명보다 작다면 계산할 필요가 없으므로 조건을 걸어둔다. 
• 그리고 백트래킹으로 구하다가 이미 선발된 인원이 k명이 채워진다면 c가 true로 바꿔서 이미 선택이 완료된 경우 재귀에 들어가지 못하도록 조건을 걸어둔다.

 

 

3. 삽질 & 느낀점

• 여러 조건을 걸었는데도 자꾸 시간초과가 발생하고 게시판에 있는 모든 반례를 돌렸는데 통과했다.
• 하지만 알고 보니깐 dfs 내에서의 조건보다 백트래킹을 시작하는 입구부분에서 맨 처음의 사람이 친구가 k명 이상이 되는지 여부에 따라서도 재귀를 탈지말지 결정하는 부분이 중요 포인트였던 것이었다.
• 앞으로 백트래킹을 풀 때 dfs 내에 조건 뿐만 아니라 밖에서의 조건도 고려해서 문제를 풀어봐야겠다고 느꼈다.

 

💻 소스코드 (JAVA)

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

public class Main_2026 {
    public static int k, n, f;
    public static boolean c = false;
    public static boolean[][] check;
    public static int[] friend_num;
    public static int[] friend;
    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());
        f = Integer.parseInt(st.nextToken());
        check = new boolean[n+1][n+1];
        friend_num = new int[n+1];
        for(int i=0;i<f;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            check[a][b] = true;
            check[b][a] = true;
            friend_num[a]++;
            friend_num[b]++;
        }
        friend = new int[k];
        boolean[] visited = new boolean[n+1];

        for(int i=1;i<=n;i++) {
            if(friend_num[i] < (k-1)) continue;
            dfs(1, i, visited);
            if(c) break;
        }
        if(!c) System.out.println(-1);
    }

    public static void dfs(int depth, int node, boolean[] visited){
        if(c) return;
        visited[node] = true;
        if(depth == k){
            c = true;
            for(int i=1;i<=n;i++){
                if(visited[i])
                    System.out.println(i);
            }
            return;
        }
        for(int i=1;i<=n;i++){
            if(visited[i] || !check[node][i]) continue;
            if(c) return;
            if(i != node && isfriend(visited, i)){
                dfs(depth+1, i, visited);
            }
        }
        visited[node] = false;
        return;

    }

    public static boolean isfriend(boolean[] visited, int node){
        for(int i=1;i<=n;i++){
            if(visited[i]){
                if(!check[i][node]) return false;
            }
        }
        return true;
    }

}