백준 15650 N과 M(2) - 백트래킹문제

15650번: N과 M (2) (acmicpc.net)

15650번: N과 M (2)

N과 M문제와 매우 비슷 but 오름차순만 정렬해야된다는 것이 달랐음.

N,M = map(int, input().split())
lst = []
visited = [False] * N
def dfs(depth):
    if depth == M:
        print(' '.join(map(str, lst)))
        return
    for i in range(N):
        if not visited[i]:
            for j in range(i+1):
                visited[j] = True
            lst.append(i + 1)
            dfs(depth + 1)
            for j in range(i+1):
                visited[j] = False
            lst.pop()
dfs(0)

나의 아이디어: 기존것을 다 True로 만들면... 더이상 그쪽은 가지 않으니까 오름차순 정렬할것이다.

결과: 맞긴 함.. 그런데 뭔가 더 효율적인 방법이 있을듯

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)

결론은 요렇게! 원래는 매 반복문마다 for i in range(N+1) 요랬다면 이번엔 걍 지금의 depth부터 참조를 시작하면 알아서 거기부터 판단하기 시작함.

그러므로 for i in range(start, n+1)이런식으로 됨

간단하네... 새로운걸알았다.

역시 백트래킹 같은 알고리즘은 걍 하면 할수록 깨닫는군.....

아직은 진짜 기본문제지만 점차 익혀가자