[백준 2026] 소풍 (C++, Java)

문제 링크: https://www.acmicpc.net/problem/2026

2026번: 소풍

1. 주의할 점

- 전체 학생에 대해 DFS를 돌리지 않도록 한다

 

2. 구현

- Arr[][] 배열을 통해 학생간 친구관계를 저장한다

- 각 학생에 대해 친구가 N-1명 이상인 경우에만 DFS를 수행하도록 하기 위해 Avail에 친구가 N-1명 이상인 학생만 담는다

- DFS()를 통해 N명을 골랐을때 모두 친구면 Fin을 True로 설정하여 더 이상 검사하지 않도록 한다

- 만족하는 경우가 없다면 -1을 출력한다

 

[C++]

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
bool arr[901][901] = { false, };
int num, n, f, a, b;
vector<int> avail, v, ans;
bool fin = false;

void dfs(int idx, int cnt) {
	if (fin) return;
	if (cnt == n) {
		bool canGo = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				if (!arr[v[i]][v[j]]) {
					canGo = false;
					break;
				}
			}
			if (!canGo) break;
		}
		if (canGo) {
			fin = true;
			ans = v;
		}
		return;
	}
	for (int i = idx; i <avail.size(); i++) {
		v.push_back(avail[i]);
		dfs(i + 1, cnt + 1);
		v.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> num >> f;
	for (int i = 0; i < f; i++) {
		cin >> a >> b;
		arr[a][b] = true;
		arr[b][a] = true;
	}
	for (int i = 1; i <= num; i++) {
		int cnt = 0;
		for (int j = 1; j <= num; j++)
			if (arr[i][j]) cnt++;
		if (cnt >= n - 1) avail.push_back(i);
	}
	dfs(0, 0);
	if (!fin) cout << -1;
	else {
		for (int a : ans)
			cout << a << '\n';
	}
	return 0;
}

 

[Java]

import java.util.*;
import java.io.*;

public class 소풍{
	static boolean arr[][],finish;
	static int willGo, num, relation;
	static List<Integer> li;
	static int temp[],ans[];
	
	static void dfs(int idx, int cnt) {
		if(finish) return;
		if(cnt==willGo) {
			boolean canFin = true;
			for(int i=0;i<willGo;i++) {
				for(int j=0;j<willGo;j++) {
					if(i==j) continue;
					if(!arr[temp[i]][temp[j]]) {
						canFin=false;
						break;
					}
				}
				if(!canFin) break;
			}
			if(canFin) {
				finish=true;
				ans = temp.clone();
			}
			return;
		}
		for(int i=idx;i<li.size();i++) {
			temp[cnt]=li.get(i);
			dfs(idx+1,cnt+1);
			temp[cnt]=0;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		
		willGo = Integer.parseInt(st.nextToken());
		num = Integer.parseInt(st.nextToken());
		relation = Integer.parseInt(st.nextToken());
		
		//초기화
		arr = new boolean[num+1][num+1];
		li = new ArrayList<>();
		temp = new int[willGo];
		ans = new int[willGo];
		finish=false;
		
		for(int i=0;i<relation;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a][b]=true;
			arr[b][a]=true;
		}
		
		for(int i=1;i<=num;i++) {
			int cnt = 0;
			for(int j=1;j<=num;j++) 
				if(arr[i][j]) cnt++;
			if(cnt>=willGo-1)
				li.add(i);
		}
		
		dfs(0,0);
		if(!finish) System.out.println(-1);
		else {
			for(int a: ans)
				System.out.println(a);
		}
	}
}