[파이썬] 백준 연습문제 #15549. N과 M 완벽해설

 

문제

 

 

해설

 

이 문제는 백트래킹(Backtracking)을 사용해서 푸는 가장 기본적인 문제이다.

 

백트래킹은 재귀적 방법을 통해 모든 경우의 수를 탐색하는 알고리즘으로, 알고리즘 문제에서 정말 자주 출제가 되는 유형이다. 백트래킹을 부르는 다른 용어로는 깊이 우선 탐색 (DFS: Depth First Search), 재귀 함수 등이 있다.

 

 

 

백트래킹, 즉 깊이 우선 탐색은 위의 사진과 같이 모든 경우의 수를 깊게 들어갔다가 나오는 방식으로 진행이 되는 알고리즘이다. 즉 이 문제의 경우는 1에서 4까지의 수열을 구한다고 치면 1이라는 값을 처음으로 넣었을 때 다음 깊이의 탐색에서는 2, 3, 4 중 하나를 넣고, 만약 3을 넣었다고 한다면 다음 깊이에서는 2, 4 중 하나를 넣고, 여기서 4를 골랐다면 마지막으로 2를 넣어서 모든 경우의 수를 이렇게 하나하나 체크하게 된다.

 

 

# 백트래킹 함수 (재귀적 함수)
# - 입력값 
#    1. 이전까지 누적으로 담은 리스트 path
#    2. 숫자 N
#    3. 수열의 갯수 M
def backtracking(path, N, M):
    # 종결조건을 넣어준다. (즉 이 함수가 끝나는 조건을 넣어준다.)
    # 이 문제의 경우 수열 4개가 완성될 때가 종결 조건이다.
    if (len(path) == M):
        # 수열의 각 요소를 문자형으로 바꿔준다.
        path = list(map(str, path))
        # 그리고 프린트해준다.
        print(" ".join(path))
        # 마지막으로 함수를 끝내준다. 
        # (종결조건 안에 return이 없을 경우 함수가 무한으로 돌아간다. 따라서 무조건 넣을 것.)
        return

    for i in range(1, N+1):
        if (visited[i] == 0):
            path.append(i)
            visited[i] = 1
            backtracking(path, N, M)
            visited[i] = 0
            path.pop()

 

그 생각을 코드로 작성하면 위와 같게 된다. 백트래킹은 함수를 끝내도록 하는 "종결조건"이 가장 앞에 위치하고, 그 다음으로는 함수 안에서 함수를 다시 한번 더 돌리는 코드가 위치하게 된다. 하지만 이렇게 함수 안에서 함수를 다시 돌리는 코드는 잘못하면 무한하게 함수가 돌아가는 문제가 발생하게 되는데, 이러한 무한 함수 문제를 해결해주기 위해서 종결조건을 꼭 넣어주어야만 하고, 종결조건 안에 함수를 끝마치는 return 을 무조건 넣어주어야만 한다.

 

 

            path.append(i)
            visited[i] = 1
            backtracking(path, N, M)
            visited[i] = 0
            path.pop()

 

그 외의 특징으로는 backtracking을 하기 전에 필요한 처리를 할 때, backtracking을 하고 나서는 그 필요한 처리를 다시 원상회복시켜주어야만 한다. 

 

 

 

그 이유는 위의 사진을 통해 설명하자면, backtracking 함수가 끝났다는 것은 결국 3번 방향으로 가서 G를 이미 탐색하고 4번으로 돌아오는 과정이기 때문에 G에 대해서 처리해준 값들을 모두 다시 원상회복 시킨 후 H로 탐색을 다시 진행해야만 하기 때문이다. (이해하기가 어려운 내용이라서, 이해가 어려울 시에는 그냥 위의 사용법을 그대로 외운 후, 여러 문제들을 풀어보면서 그 감을 익히면 좋다.)

 

아무튼 이러한 원리를 통해 백트래킹 함수를 짤 수가 있다.

 

그리고 한가지 더 알아두면 좋을 점은, 코드에서 방문표시 "visited"를 사용하게 되면 각각의 요소를 딱 한번만 사용할 수 있도록 규제해줄 수 있고, 만약 이 "visited"를 사용하지 않으면 각각의 요소를 중복으로 사용할 수 있게 된다.

 

 

예를 들어 위의 결과값은 visited를 사용했을 때이다. 보면 각각의 요소가 중복되지 않도록 수열이 만들어진 것을 알 수 있다.

 

 

 

반면에 위의 결과값은 "visited"을 아예 다 빼주었을 때의 결과물이다.  이렇게 되면 중복도 허용하면서 수열이 만들어진다.

 

 

코드

 

import sys

# 입력값을 받아들인다.
N,M = map(int, sys.stdin.readline().split())
# 각각의 숫자의 방문표시를 체크하기 위해서 visited 리스트를 준비해준다.
visited = [0 for _ in range(N+1)]

# 백트래킹 함수 (재귀적 함수)
# - 입력값 
#    1. 이전까지 누적으로 담은 리스트 path
#    2. 숫자 N
#    3. 수열의 갯수 M
def backtracking(path, N, M):
    # 종결조건을 넣어준다. (즉 이 함수가 끝나는 조건을 넣어준다.)
    # 이 문제의 경우 수열 4개가 완성될 때가 종결 조건이다.
    if (len(path) == M):
        # 수열의 각 요소를 문자형으로 바꿔준다.
        path = list(map(str, path))
        # 그리고 프린트해준다.
        print(" ".join(path))
        # 마지막으로 함수를 끝내준다. 
        # (종결조건 안에 return이 없을 경우 함수가 무한으로 돌아간다. 따라서 무조건 넣을 것.)
        return

    for i in range(1, N+1):
        if (visited[i] == 0):
            path.append(i)
            visited[i] = 1
            backtracking(path, N, M)
            visited[i] = 0
            path.pop()

backtracking([], N, M)

 

 

결과