알고리즘 마라톤 6일차

35번

N과 M (2)

일단, 이 문제를 잘 이해하기 위해서는 아래 문제부터 푸는 것이 좋을 것 같다.
N과 M (1)

n, m = list(map(int, input().split()))
s = [] # m개의 수열을 저장하기 위한 리스트

def dfs():
    if len(s) == m: # 수열이 m개가 되면 모든 숫자를 출력하고 리턴
        print(' '.join(map(str, s)))
        return

    for i in range(1, n + 1): # 1부터 n까지의 숫자들을 모두 확인
        if i not in s: # 중복이 아닐 경우에만 숫자 넣기
            s.append(i)
            dfs()
            s.pop()

dfs()

만약 여기서 n=4, m=2이면 i = 1부터 s=[1] → 재귀 → s=[1,2] → 재귀 → 출력 → pop → s=[1] → 재귀 → s=[1,3] → 재귀 → 출력 → pop → s=[1] → 재귀 → s=[1,4] → 재귀 → 출력 → pop → pop → i = 2일 때 ... 식으로 진행된다.

N과 M(2) 문제에서는 여기에 [1,2], [2,1] 같은 경우는 중복되는 경우로 보고 [1,2]만 출력해야한다.

재귀 호출 시에는 자기 다음 숫자를 불러오는 식으로 앞의 숫자가 뒤의 숫자보다 작은 경우를 제외시켰다.

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)

36번

N-Queen

N × N인 체스판 위에 퀸 N개가 있고, 그 퀸들끼리 서로 공격할 수 없게 놓는 경우의 수를 출력하면 되는 문제다.
서로 공격할 수 없게 놓으려면 퀸의 직선이나 대각선 위에 다른 퀸이 놓여 있는지 여부를 검사해야 한다.

백트래킹 관련 문제가 계속 나오고 있어서 백트래킹에 대한 개념을 정리해보자면
백트래킹이란 DFS + 가지치기다. DFS는 재귀로 문제를 푸는 것을 의미하고, 가지치기는 중간에 break나 continue 등을 사용하여 불필요한 재귀호출을 막는 것을 의미한다.

너무 어렵다...

37번

계단 오르기

38번

터렛

39번

블랙잭

40번

분해합

6번

셀프 넘버

11번

Fly me to the Alpha Centauri