백준 2026. 소풍 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/2026

"DFS 문제를 잘 읽어야함..."

문제를 잘 안 읽어서 계속 틀렸음. 문제를 잘 읽어 보면 선택된 K명의 모든 애들이 다 친구여야 함.

최초에 1-3-2-4 의 관계가 되면 나는 1,2,3,4 모두 답으로 출력했음. 이거 빼고는 그냥 DFS 문제.

따라서 아래 68~ 73 라인을 추가했음.

팁으로 경로를 찍을 때는 list 보다는 아래와 같이 result 배열 하나만을 생성해 이를 이용해 경로를 찍는 것이 더 좋다고 생각됨.

또 하나, 전부 친구인지 아닌지 판별하는 부분에서 boolean 변수를 사용할 수도 있지만 이미 생성된 j를 가지고 끝까지 돌았는지 j == index 인지 판별하면 변수 생성을 하나 줄일수 있으미..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    static int K,N,F;
    static int[][] adj;
    static int[] result;
    static boolean find;
    static StringBuilder sb = new StringBuilder();
    
    public static void main (String[] args) throws IOException  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());
        
        result = new int[K];
        adj = new int[N+1][N+1];
        
        for (int i = 0; i < F; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // a와 b가 친구라면 b와 a도 친구
            adj[a][b] = adj[b][a] = 1;
        }
        
        for (int i = 1; i <= N; i++) {
            result[0] = i;
            solve(1,i);
            // 다 찾았다면 종료
            if(find) break;
        }
        // 가능한 결과를 찾은 경우에만,
        if(find){
            for (int i = 0; i < K; i++) {
                sb.append(result[i]+"\n");
            }
            System.out.print(sb.toString());        
        }
        else {
            System.out.println(-1);
        }
    }
    
    static void solve(int index, int cur) {
        // 결과 찾으면 탐색 x
        if(find) return;
        
        // 마지막 K번째까지 다 돌한 경우 종료.
        if(index == K) {
            find = true;
            return ;
        }
        
        for (int i = cur+1; i <= N; i++) {
            
            // 애초에 cur과 i가 친구가 아니면 패스
            if(adj[cur][i] == 0) continue;
            
            // 지금까지 선택된 모든 친구들과 i가 친구인지 판별하여
            int j;
            for (j = 0; j < index; j++) {
                if(adj[i][result[j]] == 0) break; 
            }
            // 전부 친구가 아니라면 패스
            if(j == index) continue;
            
            result[index] = i;
            solve(index+1,i);
            if(find) return ;
        }
    }
}