[python_파이썬_Half Pass]백준_15650번_N과 M(2)_백트래킹_풀이

공부하는허딩크 : https://www.youtube.com/live/zD3naTrHxto?feature=shared

 

아직 백트레킹이 익숙치 않아서 역시나 itertools로 해결했다.

 

이번에는 순서를 고려할 필요가 없어 combinations로 해결했다.

 

<첫번째 코드 : 맞았습니다.:>

N, M = map(int, input().split())

nums = list(i for i in range(1, N + 1))

NUMS = list(itertools.combinations(nums, M))

for i in NUMS:

    print(*i)

 

<스터디원 풀이 참고>

이 코드가 참 마음에 든다. 깔끔하다.

N, M = map(int, input().split())

def dfs(seq, start):

    if len(seq) == M:

        print(*seq)

        return

    for i in range(start, N + 1):

        dfs(seq + [i], i + 1)

dfs([], 1)

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

visit = [False for _ in range(n + 1)]

visit [0] = True

def dfs(result, visit, k):

    if len(result) == m:

        print(*result)

        return

   

    for i in range(k+1, n+1):

        if visit[i] == False:

            visit[i] = True

            dfs(result + [i], visit, i)

            visit[i] = False

dfs([], visit, 0)

 

<내용 복습>

1. 첫번째 문제를 활용해서 조금 수정해보았다.

아래의 건은 매번 sorted를 해주고 중복을 방지하는 방법인데 답은 나오고, 백준에서도 통과는 되지만,

기존 itertools대비 시간이 거의 5대다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

res = []

temp = []

def combinations():

    temp_sort = sorted(temp)

    if len(temp) == M and temp_sort not in res:

        res.append(temp_sort)

        return

   

    for i in range(1, N + 1):

        if not i in temp:

            temp.append(i)

            combinations()

            temp.pop()

       

combinations()

for i in res:

    print(*i)

 

2. sorted미사용 재귀 조건을 건다. 배열(a, b)만들때 b가 a보다 무조건 + 1이상이 되도록

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

visited = [False for _ in range(N + 1)]

def combinations(seq, start):

    if len(seq) == M:

        print(*seq)

        return

   

    for i in range(start, N + 1):

        if visited[i] == False:

            visited[i] = True

            combinations(seq + [i], i + 1)

            visited[i] = False

combinations([], 1)

 

3. 더 간단하게.

따로 변수를 만들 필요 없이 재귀함수 안에 조건을 넣어서 확인 후 출력하게 설계했다.

스터디원들 똑똑하네 ㅎ

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

def combinations(seq, start):

    if len(seq) == M:

        print(*seq)

        return

   

    for i in range(start, N + 1):

        combinations(seq + [i], i + 1)    

   

combinations([], 1)