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

예제 입력 1 복사

4 6 8 1 2 1 3 1 6 2 3 2 6 3 6 4 5 5 6

예제 출력 1 복사

1 2 3 6

---

K명의 서로 친구인 학생을 골라야 하는 백트래킹 문제이다.

처음엔 K명이 서로 연결되어 있으면 되는 줄 알고 풀었다가 틀렸습니다가 떴다.

1 - 2 - 3 - 6 이렇게 친구로 연결되면 되는 게 아니라, 1 - 2 - 3 - 6 이면서 1 - 3, 1 - 6,  2 - 6까지 모두 친구 관계여야 한다.

 

해결 방법은 한 명씩 백트래킹으로 조사하는 것이다. 

1번 학생부터 가능한 모든 관계를 조사해야 한다.

새로운 친구를 늘릴 땐 현재까지 친구인 학생들과도 모두 친구인지를 조사해야 한다. 

모든 학생과 친구라면 새로 친구를 늘리고, 그렇게 친구를 한 명씩 늘리면서 K명이 되면 결과 벡터에 친구들을 모두 기록하고 return 한다. 인덱스를 idx+1 부터 N까지 차례대로 증가시키기 때문에 결과 벡터는 항상 정렬된 상태로 저장된다.

 

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%86%8C%ED%92%8D%20(2026%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

  
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int K, N, F;
int p[901][901];
int visit[901];
vector<int> res;

void dfs(int idx, int cnt, vector<int> cur) {
	if (!res.empty()) return;
	if (cnt == K) {
		res = cur;
		return;
	}

	for (int i = idx + 1; i <= N; i++) {
		if (visit[i] == 1) continue;
		bool isFriend = true;
		for (int j = 0; j < cur.size(); j++) {
			if (p[cur[j]][i] == 0) {
				isFriend = false;
				break;
			}
		}
		if (isFriend) {
			visit[i] = 1;
			cur.push_back(i);
			dfs(i, cnt + 1, cur);
			cur.pop_back();
			visit[i] = 0;
		}
	}
}

int main()
{
	cin >> K >> N >> F;
	for (int a, b, i = 0; i < F; i++) {
		cin >> a >> b;
		p[a][b] = p[b][a] = 1;
	}

	for (int i = 1; i <= N; i++) {
		if (!res.empty()) break;
		visit[i] = 1;
		dfs(i, 1, { i });
		visit[i] = 0;
	}
	
	if (res.empty()) cout << "-1";
	else {
		for (int x : res)
			cout << x << "\n";
	}
		
}