[BOJ] 2026 - 소풍 (Python)

 

 

아이디어

 

백트래킹으로 현재 포함된 학생들 모두의 친구이면서 번호가 가장 작은 학생을 포함해 나간다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():

    def dfs(idx, u, li, s):
        nonlocal res
        if idx >= K:
            if not res:
                res = li
            return
        if res:
            return
        for v in range(u+1, N+1):
            if visited[v] == 0:
                if v in s:
                    visited[v] = 1
                    dfs(idx+1, v, li+[v], s&graph[v])

    K, N, F = map(int, input().split())
    graph = [set() for _ in range(N+1)]
    for _ in range(F):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)
    res = []
    for i in range(1, N+1):
        visited = [0]*(N+1)
        visited[i] = 1
        dfs(1, i, [i], graph[i])
    if res:
        print(*res, sep='\n')
    else:
        print(-1)

solution()