117. 15649( N과M(1) )

N,M = map(int, input().split())
visited = [False] * N
tmp = []

def DFS(N,M,depth):
    if depth == M:
        print(' '.join(map(str,tmp)))
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            tmp.append(i + 1)
            DFS(N, M, depth + 1)
            visited[i] = False  
            tmp.pop()    

DFS(N,M,0)

문제요약

DFS를 이용하여 백트래킹을 해보아라.

설명

DFS와 백트래킹에 대한 개념은 아래를 참고하자.

https://smhope.tistory.com/309

백트래킹

https://smhope.tistory.com/307

깊이 우선 탐색(DFS)

간단히 설명하면

N까지 탐색 후 출력하는 문제이다.

이해하기 쉽게 depth(깊이)를 정의해주었으며, 파이썬에서는 깊이 없이 구현이 가능하다.

 

4 2가 들어왔을 경우를 예를 들어 보겠다.

깊이는 2까지 탐색을 하고 숫자는 1~4가 있는 것이다.

 

그러면 먼저 0에서 1을 탐색하고, 깊이가 2이기 때문에 1, 2 를 출력한다.

0에서 2를 탐색하고 1, 3을 출력한다.

0에서 3을 탐색하고 1, 4를 출력한다.

 

다시 한번 설명하면

0 에서 1을 탐색하면 어느 공간에 1 , 0이 저장되어있다.

깊이가 2이므로 더 이상의 탐색은 끝내고 1을 내 뱉으며 0으로 돌아간다.

다음은 0 에서 2를 탐색한다.

그러면 어느 공간에 2 , 0이 저장된다.

깊이가 2이므로 더 이상의 탐색은 끝내고 2를 내 뱉으며 0으로 돌아간다.

 

즉, 스택(FILO 선입후출) 형태로 로직이 진행되는 것이다.

 

위 과정을 그림으로 설명하면,

이런식으로 진행된다.

 

코드가 작동하는 것을 그리면

다음과 같이 진행된다.

            visited[i] = False

이 구문이 있기 때문에 백트래킹이 발생하는 것이며, 이 구문이 없다면 1회 방문 후 종료가 된다.

 

추가

깊이를 M 으로 사용하여 코드를 보다 간결하게 만들 수 있다.

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

S = []

def DFS():
    if len(S) == M:
        print(' '.join(map(str,S)))
        return
    for i in range(1, N+1):
        if i not in S:
            S.append(i)
            DFS()
            S.pop()

DFS()