[백준] 소풍

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

2026번: 소풍

풀이법이 잘 생각나지 않아서 알고리즘 분류를 확인하고 푼 문제입니다. 딱히 떠오르는 풀이법이 없어서 완탐이나 백트래킹으로 접근해야하는 것은 알고 있었는데 시간초과가 나지는 않을까 생각이 들어 쉽게 시작하지 못했습니다. 특히, 백트래킹의 경우에는 시간복잡도를 예측하기가 쉽지 않은 것 같습니다.

 

풀이법은 간단합니다. 현재 학생과 친구여야만 하는 목록들을 넘겨주고 이를 만족하지 못하면 같이 소풍을 갈 수 없습니다.

 

import sys
from collections import defaultdict
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

k, n, f = tuple(map(int, input().split()))

graph = defaultdict(list)

isFriend = [
    [False] * (n + 1)
    for _ in range(n + 1)
]

for i in range(f):
    a, b = tuple(map(int, input().split()))

    # 이미 친구인 경우
    if isFriend[a][b] or isFriend[b][a]:
        continue

    graph[a].append(b)
    graph[b].append(a)

    isFriend[a][b] = True
    isFriend[b][a] = True

# 본인은 자기자신과 친구다.
for i in range(1, n + 1):
    isFriend[i][i] = True

# 친구의 번호 오름 차순으로 정렬한다.
for key in graph.keys():
    graph[key].sort()

visited = None

flag = False

def backTracking(cur, friends):
    global flag

    # 정답을 찾은 경우
    if flag:
        return

    # 현재까지 친구목록에 없는 친구가 있으면 리턴
    for fr in friends:
        if not isFriend[cur][fr]:
            return

    # 다음 친구가 친구여야하는 친구 목록들
    next_friends = friends + [cur]

    if len(next_friends) == k:
        for fr in next_friends:
            print(fr)

        flag = True
        return

    for next_friend in graph[cur]:
        if visited[next_friend]:
            continue
            
        visited[next_friend] = True
        backTracking(next_friend, next_friends)

for i in range(1, n + 1):
    visited = [False] * (n + 1)

    #이미 탐색한 곳들은 미리 방문처리해준다.
    for j in range(i):
        visited[j] = True

    visited[i] = True
    backTracking(i, [])

if not flag:
    print(-1)