BOJ 2026번: 소풍

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

2026번: 소풍

백트래킹 문제가 항상 어렵다... 재귀 싫어....

일단 재귀를 사용할 때는 먼저 탈출조건을 적은 후에 차근차근 생각하면 될 것 같다.

1. 먼저 조건을 체크하고, 조건에 맞으면 ans에 추가한다.

2. ans의 길이가 K가 되면 끝낸다.

3. dfs에서 탈출했을 때 pop해야한다.

import sys
input = sys.stdin.readline

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

for _ in range(F):
    a, b = map(int, input().split())
    friends[a][b] = friends[b][a] = 1
    
ans = []
def dfs(v):
    if (len(ans)==K):
        for i in ans:
            print(i)
        sys.exit(0)
    
    for i in range(v+1, N+1):
        if (friends[v][i]==1):
            flag = True
            for j in ans:
                if (friends[i][j]!=1):
                    flag = False
                    break
            if (flag==True):
                ans.append(i)
                dfs(i)
    ans.pop()

    return
for i in range(1,N+1):
    ans.append(i)
    dfs(i)
    #ans.pop()
print(-1)

dfs안에서 pop을 해주기 때문에 호출하는 부분에서는 pop을 할 필요가 없다.