[자바] 백준 2026 - 소풍 (java)

목차

문제 : boj2026

 

 

필요 알고리즘

• 브루트포스, 백트래킹
  
  • 백트래킹을 써서 모든 경우를 살펴보면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  그냥 백트래킹 섞어서 브루트포스로 해보고 안되면 다른 방법을 찾으려고 했는데 통과됬다. 초기 명분(?)은 어차피 최악의 경우 K가 62일 경우, 최소로 필요한 간선은 62*61 = 3782개인데 F가 최대 5600이라서 최악의 경우라도 5600개 중 3782개가 쓰여야 되므로, 다시 백트래킹으로 되돌아와서 다음 경우의 수를 보는 경우가 그리 많지 않아서 그냥 백트래킹 섞은 브루트포스로 진행해도 대충 시간이 될거라 생각했다. 수학이 약햇4ㅓ 백트래킹이 포함된 경우 시간복잡도를 어떻게 계산해야하는지는 잘 모르겠다. ㅠ

 

  로직은 이하와 같았다.

1. dfs를 진행하면서 낮은 번호부터 차례대로 하나씩 고른다. 일단 여기서 순서를 증가하는 순서로 고정함으로써 시간을 많이 줄일 수 있다.

2. '1'에서 번호를 고를 때, 현재까지 고른 모든 숫자와 친구인지 확인한다. (만약 간선이 단방향이었다면 이렇게 할 수 없고, 우선 k개를 고른 후에 확인해야 했는데 양방향이라서 매번 확인해도 최종적으로 고른 k개를 서로서로 모두 확인한것과 동일한 효과이다.)

3. 현재까지 고른게 k개라면 출력하고 끝낸다.

4. k개를 고르는게 불가했다면 -1을 출력한다.

 

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    int k, n;
    Set<Integer>[] friends;

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        int f = Integer.parseInt(st.nextToken());

        if (n < k) {
            System.out.println(-1);
            return;
        }

        friends = new Set[n+1];
        for (int i = 1; i <= n; i++) friends[i] = new HashSet<>();

        while (f-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            friends[a].add(b);
            friends[b].add(a);
        }

        int[] selected = new int[k];
        if (!dfs(0, 0, selected)) {
            System.out.println(-1);
        }
    }

    private boolean dfs(int cnt, int bf, int[] selected) {
        if (cnt == k) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < selected.length; i++) sb.append(selected[i]).append('\n');
            System.out.print(sb);
            return true;
        }

        for (int i = bf+1; i <= n; i++) {
            boolean canBeFriend = true;
            for (int j = 0; j < cnt; j++) {
                if (!friends[i].contains(selected[j])) {
                    canBeFriend = false;
                    break;
                }
            }
            if (!canBeFriend) continue;

            selected[cnt] = i;
            if (dfs(cnt+1, i, selected)) return true;
        }

        return false;
    }
}