[백준] 2026 - 소풍

[문제링크]

2026번: 소풍

 

0. N명의 학생들 중 K명을 선택했을때, 모든 학생들이 친구여야 한다

  - 아무나 두 명 뽑더라도 이 둘은 항상 친구여야 한다

 

1. 재귀적으로 이전에 선택한 X와 친구인 Y로 진행하되, 지금까지 선택해온 사람들 전부와 Y가 친구일때만 진행한다

 

2. 목표인 K명에 도달하면 완성, 종료한다

  - 가능한 학생 번호가 작은 결과를 내야 하므로, 번호가 작은 학생부터 시작한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		k = pint(st.nextToken());
		n = pint(st.nextToken());
		f = pint(st.nextToken());
		
		picked = new int[k];
		
		adj = new boolean[n+1][n+1];
		Arrays.fill(adj[0], true);
		
		friendCnt=new int[n+1];
		friendCnt[0]=n;
		
		for (int i = 0; i < f; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int p1 = pint(st.nextToken());
			int p2 = pint(st.nextToken());
			
			adj[p1][p2]=true; friendCnt[p1]++;
			adj[p2][p1]=true; friendCnt[p2]++;
		}
		
		if(rec(0,0)) {
			for (int i = 0; i < k; i++) {
				System.out.println(picked[i]);
			}
		}
		else {
			System.out.println(-1);
		}
	}
	
	static int k,n,f;
	static boolean[][]adj;
	static int[] friendCnt;
	static int[] picked;
	
	static boolean rec(int cnt, int cur) {
		if(cnt==k) {
			return true;
		}
		//현재 cur의 친구를 다 반영해도 k가 안되면 탈출
		if(friendCnt[cur]< k-cnt)return false;
		
		for (int i = 1; i <= n; i++) {
			if(adj[cur][i]) {
				//i번째 사람와 친구
				boolean isF=true;
				for (int j=0; j<cnt; j++) {
					if(!adj[ picked[j] ][i]) {
						isF=false;
						break;
					}
				}
				//지금까지 찾은 모든 친구와 i도 친구면
				if(isF) {
					picked[cnt]=i;
					if(rec(cnt+1,i))return true;
					
				}
			}
			
		}
		
		return false;
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면