[백준][Python] 2026 소풍

findTheValue 2021. 9. 14. 13:53

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

2026번: 소풍

만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째

www.acmicpc.net

K명 모두가 친구여야 통과하는 dfs를 짜주면 된다.

import sys
input = sys.stdin.readline

def dfs(v,arr):
    if len(arr)==K:
        for num in arr:
            print(num)
        exit()
    for i in range(v+1,N+1):
        if not visited[i]:
            for num in arr:
                if num not in graph[i]:
                    break
            else:
                visited[i] = True
                dfs(i,arr+[i])



K, N, F = map(int, input().split())
graph = {i: [] for i in range(1,N+1)}
for _ in range(F):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

for i in range(1,N+1):
    visited = {i: False for i in range(1,N+1)}
    visited[i] = True
    dfs(i,[i])

print(-1)

저작자표시 (새창열림)