[코테준비] 순열, 조합, 백트래킹

기본적으로 순열, 조합 문제는 DFS 재귀함수를 이용해서 해결

 

순열 조합 모두 "없으면 넣고 dfs()" 구조는 똑같지만

조합의 경우 start를 고려해줘야 하는 차이가 있었음

-> s에 넣고 빼고를 반복하면서 모든 경우의 수를 돌린다

 

+ 왜 백트래킹 문제인가?

s의 개수가 M이상이 되면 그 다음 경우의 수는 파악할 필요가 없기 때문에 백트래킹 문제인 것

 

순열

# 15649번
n,m = list(map(int,input().split()))
s = []
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

조합

# 15650번
n,m = list(map(int,input().split()))
s = []
def dfs(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start,n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)

+ 23.10.08

조합을 활용한 문제의 경우 재귀함수를 통해 표현할 수도 있다.

def wall(반복 횟수):
    if 반복 횟수 == 3:
        bfs() # 조합이 완성되면 계산 후 종료
        return
    for 로우 i in range(N):
        for 컬럼 j in range(M):
            if 맵[i][j] == 0:
                맵[i][j] = 1
                wall(반복 횟수 + 1) # 재귀함수를 통해 조합을 표현
                맵[i][j] = 0

+ 23.10.11

삼성 코테는 조합 라이브러리 사용 가능하다 그냥 라이브러리 쓰자

from itertools import combinations 
array = [2, 4, 6] 
list(combinations(array, 2)) # [(2,4),(2,6),(4,6)]