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

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

 
※ 백트레킹으로 문제를 해결하는 것인데 일단 itertools.permutations로도 해결이 가능하다.
즉, 같은 내용이다. 라이브러리를 활용해서 순열을 구해서 해결할 것인지, 아니면 백트레킹으로 함수를 만들어서
재귀함수로 순열을 만들 것인지...
일단 백트레킹을 중점적으로 연습해보자!
 
수열 문구가 있어서 itertools로 풀었다.
※여기서 복습
itertools의 활용 : https://heodinkcodingdiary.tistory.com/21

[python_파이썬]itertools 학습_순열(permutions)과 조합(combinations)_풀이

1. permutations는 중복 없음, 순서 구분함 : (1, 1) 이런거 안됨, (1, 2)와 (2, 1)은 다른거임
2. combinations는 중복 없음, 순서 구분 없음 (1, 2)와 (2, 1)은 같은거임
3. combinations_with_replacement는 중복 가능, 순서 구분 없음
 
<첫번째 시도 : 맛았습니다.>
itertools기억이 가물가물해서 조금 헤맸지만 결과는 나올 수 있었다.
print할때 ' '.join(map(str, i))를 해도 괜찮다. ※ ''사이에 빈칸으로 각 출력값 사이에 빈칸 요소 빼먹지 말고!!!!

import sys

import itertools

input = sys.stdin.readline

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

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

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

for i in NUMS:

    print(*i)

 
 <중간 코드1>
import sys
input = sys.stdin.readline

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

for i in range(1, N+1):
    if len(str(i)) == M:
        print(i)
 
단 이 문제의 출제 의도는 백트래킹이다.
스터디원들은 dfs 알고리즘 + 재귀 알고리즘을 활용해서 해결했다.
 
<스터디원 코드 참고>
재귀적으로 접근해서 필요한 데이터를 출력하는 모양이다.
천천히 복습을 해봐야 겠다.

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):

    if len(result) == m:

        print(*result)

        return

   

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

        if visit[i] == False:

            visit[i] = True

            dfs(result + [i], visit)

            visit[i] = False

dfs([], visit)

 

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

res = []

seq = []

def dfs():

    if len(seq) == M:

        res.append(" ".join(list(map(str, seq))))

        return

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

        if i not in seq:

            seq.append(i)

            dfs()

            seq.pop()

dfs()

for r in res:

    print(r)

 
 
<추가 복습>
1. permutations를 대체하는 함수
재귀함수를 이용해서 중복 없고, 순서를 구분하는 M개를 가지는 조합을 만들어서 출력해주는 코드이다.
재귀가 들어갈때 depth를 이해하는데 꽤 애를 먹었다.
N = 3이고, M = 2일때
ⓑ "i = 1일때 temp = [1]이 되고, 
그 이후 다시 permutations()에 들어가서" 다시 i = 1부터 시작하는데
i = 1일때 if불만족
ⓐ "i = 2일때 if만족해서 temp = [1, 2]가 되고 다시 permutations()에 들어가지만" 바로 if 만족으로 res = ["1 2"] 들어간다.
여기서 중요한 포인트는 return이 됨으로 i = 2일때 permutations()에 들어간 다음부터 시작한다. => ⓐ 부분으로 돌아온다.
그래서 temp.pop()를 통해서 temp = [1]이 되고
i = 3일때 if만족 후 temp = [1, 3]이 되고 ⓐ와 동일한 동작을 한다.
 
다시 중요한 포인트가 i = 4일때를 지나고 temp = [1, 4]를 거쳐 temp.pop()를 통해 다시 temp = [1]이 되고 나서
다음 순서는 ⓑ로 돌아가서 다시 temp.pop()를 통해서 temp = [] 빈리스트가 된다는 점이다. => 이부분이 제일 이해하기 어려웠다.

import sys

input = sys.stdin.readline

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

res = []

temp = []

def permutations():

    if len(temp) == M:

        res.append(' '.join(map(str, temp)))

        return

   

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

        if i not in temp:

            temp.append(i)

            permutations()

            temp.pop()

permutations()

for i in res:

    print(i)

 
2. visit 변수 활용한 방문 이력 관리
일단 이 코드에서 제일 이해가 안된 부분은 result +[i] 였다. => 요소가 누적되는게 아니라 계속해서 새로운 리스트가 되는게 중요 포인트이다.
N = 3, M = 2일때
i = 1이라면 result + [i] ==> [1]이 되고, 이게다시 dfs(result, visit)으로 들어가서 result = [1]과 [2]가 만나서 새로운 result = [1, 2]가 된다. 나머지는 첫번째 permutaions랑 동일하다.

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):

    if len(result) == m:

        print(*result)

        return

   

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

        if visit[i] == False:

            visit[i] = True

            print(result)

            dfs(result + [i], visit)

            visit[i] = False

dfs([], visit)

 
3. 활용 : 그냥 다시 한번 풀어 봤는데 이렇게 나오네?

import sys

input = sys.stdin.readline

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

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

def combinations(seq):

    if len(seq) == M:

        print(*seq)

        return

   

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

        if visited[i] == False:

            visited[i] = True

            combinations(seq + [i])

            visited[i] = False

combinations([])

 

4. 추가 복습 : 공부를 지속적으로 하지 못해서 1주일 이후 다시 봤는데 기억이 안나서 복습하다가 다시 풀어 보았다.

아래와 같이 효율적인 코드가 나온다.

import sys

input = sys.stdin.readline

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

def per(seq):

    if len(seq) == M:

        print(*seq)

        return

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

        if i not in seq:

            per(seq + [i])

           

per([])