[백준 파이썬] # 15649 N과 M (1)

Silver III

# 15649 N과 M (1)

링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

풀이

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

def dfs(depth, seq):
    if depth == M:
        print(' '.join(list(map(str, seq))))

    for i in range(1, N+1):
        if i not in seq:
            temp = seq.copy()
            temp.append(i)
            dfs(depth+1, temp)

dfs(0, [])

 

후기

• 두 세번 복습하고 있는데 개념이 잘 들어오진 않는게 사실.. (복습하자 복습..!)
• 다른 블로거 분의 풀이를 참고해서 위 풀이로 학습했다.
• 백트래킹은 DFS 구조를 기반으로 한다. 그래프를 그려서 구조를 파악하자

 

---

 

풀이 수정 1차

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

def dfs(depth, seq):
    if depth == M:
        print(' '.join(list(map(str, seq))))
        return
    
    for i in range(1, N+1):
        if i not in seq:
            seq.append(i)
            dfs(depth+1, seq)
            seq.pop()

dfs(0, [])

 

• 좀 더 이해가 잘 되는 방법으로 수정해보았다.
• dfs의 if depth==M 절에 해당하게 되면 print를 하고 return에 의해 dfs(depth+1, seq)과정으로 돌아간다. 
• seq.pop()에 의해 seq 리스트 마지막 요소가 빠지게 되고, for 문에 다음 숫자가 채워진다.
  • depth=4, N=2 일때 예시) [1] → [1, 2] → if절 충족, print와 return 적용된 상태에서 재귀함수 전으로 돌아감 → pop 적용 : [1] → for문으로 다음 i에 대해 탐색 : [1, 3] → [1] → [1, 4] → [2] → ... 
• 설명하기란 참 쉽지 않다.

 

---

 

풀이 수정 최종

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

def dfs(start, seq):
    if len(seq)==M:
        print(' '.join(list(map(str, seq))))
        return
    
    for i in range(1, N+1):
        if i not in seq:
            seq.append(i)
            dfs(start+1, seq)
            seq.pop()
            
dfs(0, [])