[BOJ/백준] 2026 소풍 파이썬

문제 링크 : https://www.acmicpc.net/problem/2026

2026번: 소풍

 

처음에 문제 조건을 잘못이해해서 틀렸었다.

나는 a-b, b-c라면 a-c도 친구라고 이해하고 풀었더니 63%였나 그쯤에서 틀렸다고 나왔다.

그래서 예제를 찾아보고 돌려보니 a-b, b-c라면 a-c라는 관계도 있어야한다.

즉 모든 친구가 서로서로 모두 친구사이어야한다. 건너서 친구면 친구가 아닌 것이다.

 

우선 나는 BFS로 풀었다.

사용하는 자료구조는 우선순위큐와 인접행렬, 인접리스트를 사용 사용했다.

인접행렬은 두 학생이 친구관계인지 체크하기 위함이고, 인접 리스트는 친구 목록이 필요하기 때문이다.

우선순위큐는 친구의 번호를 작은것 부터 접근해야하기 때문이다.

자신의 친구들을 접근할때도 번호 순서대로 접근해야하므로 인접리스트도 정렬해서 저장해놨다.

 

이제 BFS 돌면서 본인의 친구들을 체크한다. 방문하지 않았고, 현재 이전에 방문한 친구들과 현재 방문하려는 친구와도 친구관계인지 체크한 후 큐에 넣어주고 방문한 친구 배열에 번호를 넣어준다.

BFS 돌다가 친구의 수가 k개라면 종료 출력하면 된다.

 

from sys import stdin
from heapq import heappush,heappop

input = stdin.readline

k,n,f = map(int, input().split())
adj_list = [[] for _ in range(n+1)]
adj_mat = [[False]*(n+1) for _ in range(n+1)]

for _ in range(f):
    a,b = map(int, input().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

    adj_mat[a][b] = adj_mat[b][a] = True

for idx in range(1,n+1):
    adj_list[idx].sort()
end = -1
def solv():
    for start in range(1,n+1):
            rst = bfs(start)
            if rst:
                rst.sort()
                for num in rst:
                    print(num)
                return
    print(-1)

def bfs(start):
    visited = [False]*(n+1)
    path = [start]
    pq = [start]
    visited[start] = True
    while pq:
        now = heappop(pq)
        for nxt in adj_list[now]:
            if not visited[nxt]:
                visited[nxt] = True
                flag = False
                for target in path:
                    if not adj_mat[nxt][target]:
                        flag = True
                        break
                if not flag:
                    path.append(nxt)
                    if len(path) == k:
                        return path
                    heappush(pq,nxt)
    return None
if k == 1:
    print(1)
else:
    solv()