백준 15649,15650 N과 M(Backtracking)

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

15649번: N과 M (1)

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

15650번: N과 M (2)

def DFS():
    if len(s) == M:
        print(*s)
        return

    for i in range(1, N + 1):
        if i in s: #가지치기
            continue

        s.append(i)
        DFS()  # 함수 다시 호출
        s.pop()  # 원상복귀

N, M = map(int, input().split())
s = []  # 출력 수열 넣을 stack
DFS()

def DFS(j):
    if len(s) == M:
        print(*s)
        return

    for i in range(j, N + 1):
        if i in s: #가지치기
            continue

        s.append(i)
        DFS(i+1)  # 함수 다시 호출
        s.pop()  # 원상복귀

N, M = map(int, input().split())
s = []  # 출력 수열 넣을 stack
DFS(1)

 

백트래킹은 재귀, 스택을 써서 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행하는 기법으로

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

 

문제를 보면 딱봐도 순열(Permutation) 문제라서 

from itertools import permutations

를 써도 되지만 백트래킹 문제이기 때문에 다른 방식으로 접근해보자.

https://www.youtube.com/watch?v=Enz2csssTCs&t=1s 

이 강의를 보고 도움이 많이 되었다.

순서쌍을 이룬다는건 트리에 방문 하는지 안하는지를 판단하면 된다.

재귀함수를 이용해서 풀었으며 

i가 1,2,3동안 각각의 1,2,3이 순서대로 있기 때문에 재귀함수 형태로 코딩을 하였고

부모노드와 자식노드가 동일시 되는 경우를 피하기 위해(가지치기)

if i in s: #가지치기
	continue

 

백준 15650

15650은 오름차순이란 룰이 추가되었다.

부모노드보다 커야되는 경우가 발생해야하니까 재귀함수에 들어갈때 부모노드보다 +1 높게 자식노드를 반복하였다.

for i in range(j, N + 1):
  if i in s: #가지치기
  	continue

  s.append(i)
  DFS(i+1)  # 함수 다시 호출
  s.pop()  # 원상복귀