bj15649 N과 M(1)

음... N queen 문제를 푼 알고리즘과 똑같은 backtracking으로 풀었다.
사실 backtracking 문제는 조건식을 만드는 것이 핵심인 것 같다.

이 문제의 핵심은 결국 중복되는 숫자가 있는지를 판별하는 것!
N과 M의 범위도 크지 않기 때문에 그냥 n squared의 time complexity를 가져도 되겠다는 생각이 들었다. 만약 N과 M이 엄청 컸다면 복사본을 하나 만들어 sort를 한번 진행하고 binary search를 써서 nlogn으로 만들어야 했을 듯?

그래서 code는 다음과 같다!

def NM_body(card, x):
    if x == M:
        print(*card)
    else:
        for i in range(1, N + 1):
            if check_card(card, x, i) == 1:
                card.append(i)
                NM_body(card, x+1)
                card.pop()


def check_card(card, x, i):
    num = 0
    while num < x:
        if card[num] == i:
            return 0
        num += 1
    return 1


N, M = map(int, input().split())
_card = []
NM_body(_card, 0)

조건에 맞으면 append하고 recursive하게 호출!
깊이 탐색이 끝나면 pop으로 빠져나와서 loop의 다음 숫자 넣어서 조건 살펴보기!

++
code를 한번 더 수정해봤다. check_card함수의 parameter전달 인자를 줄여보았음. 이러면 memory를 조금 더 절약 가능할 듯?

def NM_body(card, x):
    if x == M:
        print(*card)
    else:
        for i in range(1, N + 1):
            card.append(i)
            if check_card(card, x) == 1:
                NM_body(card, x+1)
            card.pop()


def check_card(card, x):
    num = 0
    while num < x:
        if card[num] == card[x]:
            return 0
        num += 1
    return 1


N, M = map(int, input().split())
_card = []
NM_body(_card, 0)