[BOJ/백준] 2026 소풍

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()

def checkFreinds(target_node,friend):

    for node in friend:
        if not friendly[node][target_node]:
            return False
    return True

def dfs(node,friend):
    global K,result
    if len(friend) == K:
        result = list(map(str,friend))
        sys.stdout.write('\n'.join(result))
        exit(0)
        return

    for next_node in range(node+1,N+1):
        if friend_cnt[next_node] < K-1:
            continue
        if visited[next_node]:
            continue
        if not friendly[node][next_node]:
            continue
        if not checkFreinds(next_node,friend):
            continue
        visited[next_node] = True
        dfs(next_node,friend +[next_node])
        visited[next_node] = False



K,N,F = map(int,input().split())

friendly = [[False for _ in range(N+1)] for _ in range(N+1)]

friend_cnt = [0 for _ in range(N+1)]
for _ in range(F):
    x,y = map(int,input().split())
    friendly[x][y] = True
    friendly[y][x] = True
    friend_cnt[x] += 1
    friend_cnt[y] += 1

result = []
visited = [False for _ in range(N+1)]
for num in range(1,N+1):
    if friend_cnt[num] < K-1:
        continue
    visited[num] = True
    dfs(num,[num])
    visited[num] = False

print(-1)

 이 문제는 N명 중 K명의 소풍을 보내는 것이다. 

 

단 조건이 모두가 서로 친구여야한다는 것이다.

 

그래서  N*N 친구의 관계를 나타내는 freiendly라는 행렬을 만들어 두었다.

 

서로 간에 친구관계이면 True 아니면 False가 되도록 했다.

 

이렇게 사전 준비 작업을 했다면, 백트래킹으로 문제를 접근하면 된다.

 

이 문제의 출력 조건은 만족하는 K명의 소풍을 갈수 있는 조합이 많으면 사전순으로 출력하는 것이다.

 

그러면 우리는 1번 학생부터 순차적으로 접근을 해서 만족을 하는 첫번째 K명의 조합이 사전 순으로 가장 빠른다는 것을 알 수 있게 된다.

 

여기서 재귀로 할때 주의를 해야할 것이 몇가지가 있다.

 

먼저. 현재 방문하는 친구의 친구 숫자가 K-1보다 작으면 자기를 포함해서 세도 K명이 안되기에 pass를 해주어야한다.

 

그리고, 문제의 조건 중에 소풍을 가는 친구들은 모두 친구관계 이어야한다.

 

그러므로, checkFriends 라는 함수를 통해 지금까지 뽑은 friend와 새로 방문한 next_node와 친구관계인지 파악을 해준다.

 

단 하나라도 만족하지 않으면 False를 반환해주면 된다.

 

그 뒤에는 DFS 처럼 백트래킹을 해주면 된다.

 

그리고, K를 만족하는 friend 조합이 나오면 exit로 파일을 종료하게 해준다.