백준 2026번 소풍 :: 마이구미

이번 글은 백준 알고리즘 문제 2026번 "소풍" 을 다뤄본다.

종만북이라 불리는 책에서도 나오는 문제이긴 하나, 응용된 문제이다.

문제 풀이는 DFS를 통한 백트래킹을 이용한다.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

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

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

....................

친구 관계는 상호적인 관계이므로 2번 학생이 4번 학생을 좋아하면 4번 학생도 2번 학생을 좋아한다. => 양방향

1. 학생들이 모두 서로 친구 사이라는 의미를 잘 파악해야한다.

2. 문제에서 상호적인 관계를 통해 양방향 그래프라는 힌트를 얻을 수 있다.

본인은 처음 단순히 DFS만으로 해결할 수 있을 거라 생각했다.

문제에 있어, 정점간의 연결된 간선을 잘 파악해야한다.

1 2
1 3
2 4
3 4

위와 같이 친구 관계가 주어졌으면, K명의 학생을 결정할 수 있을까?

위와 같은 그래프로 나타낼 수 있다.

연결 요소 또는 사이클이 이루어지는 모습을 볼 수 있다.

주어진 관계를 통해 1, 2, 3, 4는 소풍을 갈 수 있을까?

그렇지 않다.

문제에서는 학생들 모두 서로가 친구라고 명시했다.

즉, 아래와 같이 표현할 수 있다.

위와 같은 모습으로 성립해야한다.

결과적으로, 방문하는 정점과 방문했던 정점들 간의 친구 관계가 성립되면 DFS를 허용하면 된다.

if (k == list.size()) {
    // success
    ....................
    return;
} else {
    for (int i = v + 1; i <= n; i++) {
        if (!visited[i]) {
            boolean flag = true;
            // 서로가 모두 친구인지 체크
            for (int f : list) {
                if (!relation[i][f]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                dfs(i);
            }
        }
    }
}

static int k, n, f;
static boolean end;
static boolean[] visited;
static boolean[][] relation = new boolean[901][901];
static ArrayList<Integer> list;
static StringBuilder sb = new StringBuilder();
 
private void solve() {
    // http://mygumi.tistory.com/197
    k = sc.nextInt();
    n = sc.nextInt();
    f = sc.nextInt();
 
    for (int i = 0; i < f; i++) {
        int a = sc.nextInt();
        int b = sc.nextInt();
 
        relation[a][b] = true;
        relation[b][a] = true;
    }
 
    for (int i = 1; i <= n; i++) {
        end = false;
        list = new ArrayList<>();
        visited = new boolean[n + 1];
        dfs(i);
        if (end) {
            return;
        }
    }
    System.out.println(-1);
}
 
public static void dfs(int v) {
    if (end) {
        return;
    }
 
    visited[v] = true;
    list.add(v);
 
    if (k == list.size()) {
        for (int f : list) {
            sb.append(f + "\n");
        }
        System.out.println(sb.toString());
        end = true;
        return;
    } else {
        for (int i = v + 1; i <= n; i++) {
            if (!visited[i]) {
                boolean flag = true;
                // 서로가 모두 친구인지 체크
                for (int f : list) {
                    if (!relation[i][f]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    dfs(i);
                }
            }
        }
    }
}