코딩테스트 준비 - 백준15649번 N과 M (1)풀이-DFS에 관해서(파이썬)

---

백준 15649번 풀이

---

문제풀러가기

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

15649번: N과 M (1)

---

문제

---

풀이

  DFS알고리즘을 통해 푸는 문제이다. 

(DFS말고 다른 방법이 있다면 알려주세용 ㅠ_ㅠ)

---

코드

import sys
N, M = map(int, sys.stdin.readline().split())

arr = [i for i in range(1,N+1)]
check = [False]*len(arr)
a = []

def dfs(x):
  if x == M:
    print(*a,sep=" ")
    return

  for i in range(N):
    if check[i]:
      continue

    check[i]=True
    a.append(arr[i])
    dfs(x+1)
    a.pop() #x==M조건 만족하여 return 한다음 다시 여기로 돌아옴
    check[i] = False

dfs(0)

---

자세한 코드 풀이

아래 코드를 돌려보시면, 돌아가는 과정이 보입니다.

일단, 재귀함수 호출 시, 재귀 함수 아래내용은 위에 return으로 함수가 종료되거나, 

모든 재귀함수가 호출되고 난 후 차례대로 돌아가게 됩니다.

 

예를들어 아래에서 dfs(x+1)을 할때 dfs(x+1)아래의 식들은 일단 냅두고,  

"if x == M:
    print(*a,sep=" ")
    return" 이 식에 만족하여 return 호출을 하여 함수를 종료 했을 시, 

멈춰둔 식(제일 최근에 멈춘식)부터 실행합니다. (메아리 혹은 스택과 같은 원리로 동작)

import sys
N, M = map(int, sys.stdin.readline().split())

arr = [i for i in range(1,N+1)]
check = [False]*len(arr)
a = []

def dfs(x):
  if x == M:
    print(*a,sep=" ")
    return

  for i in range(N):
    if check[i]:
      continue

    check[i]=True
    a.append(arr[i])
    print("check:",check)
    print("a:",a)
    print("x1:",x)
    print("i1:",i)
    dfs(x+1)
    a.pop() #x==M조건 만족하여 return 한다음 다시 여기로 돌아옴
    check[i] = False
    print("after a.pop:a=",a)
    print("check:",check)
    print("x2:",x)
    print("i2:",i)
dfs(0)

코드가 이해가 안되시면 , N과 M을 정한 후 이 코드를 돌려보시며 차근 차근 대조해보시면

도움이 될거에요 :)

---

DFS 알고리즘이 궁금하다면, 아래 링크 참고해 주세요

2021.06.11 - [코딩테스트/알고리즘] - (알고리즘)DFS(Depth-First-Search) 깊이 우선 탐색 - 파이썬

(알고리즘)DFS(Depth-First-Search) 깊이 우선 탐색 - 파이썬

---

도움이 되셨다면 하트눌러주시면 감사하겠습니다 :)