백준 2026번. 소풍 (Java)

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

서로 좋아하는 친구들의 목록이 나열될 때 소풍에 보낼 수 있는 K 명의 학생을 출력하는 문제입니다.

예전에 굉장히 많이 틀려서 포기했던 문제인데 다시 푸는데도 굉장히 많은 시도를 하고 맞췄습니다..

제 기준에서 크게 두 가지의 함정이 있었는데 아래에서 설명드리겠습니다.

1. 첫번째로 주의할 점은 싸이클을 찾는 문제가 아니라는 사실입니다.

따라서 일반적인 DFS의 싸이클 검사나 유니온 파인드로는 해결할 수가 없습니다.

결국 백트래킹으로 완전 탐색을 하는데 단순하게 인접 행렬로 그래프를 구현해서 돌리면 O(n^3)으로 시간초과가 됩니다.

2. 그래서 탐색할 필요가 없는 노드를 생략하는게 두번째 핵심입니다.

탐색할 필요가 없는지는 어떻게 아는가?

소풍은 무조건 K 명이 가게 됩니다.

만약 K=4 일 때 1번 노드의 친구가 2번, 3번 밖에 없다면 그들이 모두 친구 관계여도 3이 됩니다.

결국 1번 노드는 탐색할 필요가 없어서 생략할 수 있게 됩니다.

예를 들어 K=62 일 때, 모든 노드가 60명의 친구만 가지고 있는 테스트 케이스가 주어집니다.

모든 노드들은 본인과 친구 60명을 포함해서 최대로 나올 수 있는 친구 관계가 61명이라 소풍에 가는 인원이 나올 수 없습니다.

하지만 불필요하게 모든 노드들을 탐색하고 있어야 하죠.

그래서 저는 indegree 배열을 만들어서 자신과 연결된 노드의 갯수가 몇 개인지 저장했습니다.

1번 노드의 친구가 2, 3 이면 indegree[1] = 2가 됩니다.

만약 indegree가 K-1보다 작은 노드들은 탐색할 필요 없이 생략하게 됩니다.

이렇게 두가지 예외처리를 해주면 됩니다.

	import java.util.*;
	import java.io.*;
	// https://www.acmicpc.net/problem/2026
	class Main {
	static int stoi(String s) { return Integer.parseInt(s);}
	static int[][] arr;
	static boolean[] visited;
	static int k;
	static int n;
	static int f;
	static boolean done = false;
	static StringBuilder sb;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	st = new StringTokenizer(br.readLine());
	k = stoi(st.nextToken());
	n = stoi(st.nextToken());
	f = stoi(st.nextToken());
	arr = new int[n+1][n+1];
	visited = new boolean[n+1];
	sb = new StringBuilder();
	int[] indegree = new int[n+1];
	// 인접행렬 형성
	for(int i=0; i<f; i++) {
	st = new StringTokenizer(br.readLine());
	int v1 = stoi(st.nextToken());
	int v2 = stoi(st.nextToken());
	arr[v1][v2] = arr[v2][v1] = 1;
	indegree[v1]++;
	indegree[v2]++;
	}
	// 백트래킹으로 확인
	for(int i=1; i<=n; i++) {
	// 본인 포함 k명이 되지 않으면 애초에 볼 필요가 없음
	if(indegree[i] < k-1) continue;
	if(done) break;
	visited[i] = true;
	dfs(i, 1);
	visited[i] = false;
	}
	// 아무도 소풍에 가지 못할 경우 -1
	if(!done)
	System.out.println(-1);
	else
	System.out.println(sb);
	}
	static void dfs(int now, int depth) {
	if(done) return;
	if(depth == k) {
	print();
	done = true;
	return;
	}
	for(int i=now+1; i<=n; i++) {
	if(arr[now][i] == 1 && isFriend(i)) {
	visited[i] = true;
	dfs(i, depth + 1);
	visited[i] = false;
	}
	}
	}
	// 지금까지 방문했던 노드와 현재 target 노드가 서로 친구인지 확인
	// DFS가 방문하는 점들은 항상 모두 친구임을 보장
	static boolean isFriend(int target) {
	for(int i=1; i<=n; i++) {
	if(visited[i] && arr[target][i] != 1)
	return false;
	}
	return true;
	}
	// 답 출력
	static void print() {
	for(int i=1; i<=n; i++) {
	if(visited[i])
	sb.append(i + "\n");
	}
	}
	}

view raw BOJ2026.java hosted with ❤ by GitHub