[백준 2026번] 소풍(파이썬)

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

2026번: 소풍

문제에서 설정이 누락된 게 있습니다.

'모두 친구'여야한다는 조건.

이 문제를 잘못읽으면

a-b

b-c

c-d

이렇게만 이어져있으면

소풍조라고 생각하기 쉽습니다.

하지만 이 문제가 요구하는 건

abcd이렇게 소풍조라면

a-c

a-d

b-d

이 관계도 있어야 한다는 말.

서로 건너건너 아는 것이 아니라

모두 친구여야한다는 말이 빠져있어서

저도 몇 번 헤매다가

구글링을 통해 조건을 파악했습니다.

 

#백준 2026번 소풍

K,N,F=map(int,input().split())
graph=[[]for _ in range(N+1)]

def bfs(n):
    now=graph[n]
    for go in now:
        flag=True
        for f in f_list:
            if not f in graph[go]:
                flag=False
                break
        if flag:
            f_list.append(go)

    if len(f_list)>=K:
        f_list.sort()
        for i in range(K):
            print(f_list[i])
        exit(0)



for _ in range(F):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,N+1):
    graph[i].sort()
f_list=[]
if K==1:
    print(1)
    exit(0)
for i in range(1,N+1):
    f_list=[i]
    bfs(i)
print(-1)

 

문제가 불친절해서...

그래도 그래프를 다루는 방식에 대해서

한번 공부해볼 수 있는 문제라서

한번 정리해보는 것도 좋아보입니다.