[백준 알고리즘] - N과 M(2) (15650번) with Python

📎 간략한 문제 정리

• 자연수 N과 M이 주어지고, 아래 조건을 만족하는 길이가 M인 수열을 모두 구합니다.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

📈 문제 분석

• N과 M(1)과 거의 비슷한 문제입니다. 오름차순을 이루는 부분 수열을 찾는 문제로 중복이 없고, 부분 수열의 크기가 정해진 것이 포인트입니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 사실 파이썬에는 모듈인 itertools에 combination 함수가 존재합니다. 그래서 N의 요소에서 M개를 뽑는 것은 어렵지 않지만 일부러 이 방법을 사용하지 않았습니다. 이 모듈을 사용하지 않을 때 필요한 것은 모든 요소를 접근하며 조건에 만족할 경우 결과에 넣는 작업입니다. 이 때 사용되는 백트래킹(Back Tracking) 입니다. 그 개념은 아래와 같습니다.

  

💻 풀이한 코드

from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
partial_sequence = []
visited = [False] * N
def backtracking(depth):
    if depth == M:
        print(' '.join(map(str, partial_sequence)))
    else:
        for i in range(N):
            if not visited[i] and (not partial_sequence or partial_sequence[-1] < (i+1)):
                visited[i] = True
                partial_sequence.append(i+1)
                backtracking(depth+1)
                partial_sequence.pop()
                visited[i] = False
backtracking(0)

📝 해결 과정에서 만난 문제, 고민들

• 추가된 조건을 적용하기: N과 M(1) 문제와의 차이는 결론에 순서가 있다는 점이었고, 이를 어떤방식으로 적용시킬까가 포인트였습니다. 기본적인 구조는 모두 같지만 차이는 아래 코드에서 발생합니다.

  if not visited[i] and (not partial_sequence or partial_sequence[-1] < (i+1)):

  순서를 고려하지 않을 때에는 "not visited[i]" 즉, 방문한 적 없는 숫자일 때 다음 숫자로 추가하며 진행하는 로직이었습니다. 하지만 부분 수열이 비어있거나, 채워져 있을 때 마지막 숫자보다 관찰 숫자가 더 클때에만 추가하는 로직을 통해 오름차순을 유지하게 했습니다. 예를 들어 부분 수열에 [1,4,5]가 채워져 있다면 i가 1 ~ 5일 때에는 visited의 여부에 관계없이 채워지지 않고 다음 반복으로 넘어갑니다.

  🎯 여기에서 중요한 포인트는 (not partial_sequence or partial_sequence[-1] < (i+1))입니다. 이 로직은 파이썬의 특징을 활용했습니다. 파이썬은 A or B가 있을 때, A가 참이라면 B에 관계없이 전체가 참이 되므로 B를 아예 건너뛰게 됩니다. 그래서 partial_sequence가 비어있을 경우 앞에 로직에서 참으로 처리가 되므로 partial_sequence[-1]에서 out of index Error가 발생하지 않습니다.

• 백트래킹 부분을 코드로 구현했지만 머리로 다시 한 번 그려볼 필요가 있습니다.

  visited[i] = True
  partial_sequence.append(i+1)
  backtracking(depth+1)
  partial_sequence.pop()
  visited[i] = False

  우선 if 조건문 안에 들어왔다는 이야기는 해당 숫자를 방문했다는 의미이므로 visited를 True로 바꿔줍니다. 그래서 부분 수열에 i번째 숫자(i+1)을 추가해줍니다. 여기에서 다음 깊이로 넘어가는데 이 depth+1이 의미하는 것은 부분 수열의 현재 시점 Top의 위치에 있는 숫자가 i+1이고 그 다음 요소를 넣기 위해 1부터 다시 탐색을 한다는 의미입니다.

  다시 말하면, visited[i] = True 라는 의미는 부분 수열에 이미 partial_sequence가 존재한다는 의미입니다.

  다음 로직을 살펴보면 다시 부분 수열의 마지막 요소를 pop() 해줍니다. 이를 예시를 통해 확인해보겠습니다. 예를 들어 N이 10이어서 1 ~ 10의 숫자로 M이 4인 부분 수열을 만든다고 할 때에, 현재 만들어진 부분 수열의 depth가 2이고 [3, 6]이 들어있다고 가정해보겠습니다. 이 때, i를 반복하며 조건에 맞는 7이 들어왔을 때 부분 수열은 [3,6,7]이 되고 마지막 요소를 찾아 더 진행되게 됩니다. 하지만 이렇게 끝나버리면 6 이후 7의 자리에 8, 9, 10의 요소가 들어올 수 없게 됩니다([3, 6, 8], [3, 6, 9]...). 그래서 다시 7을 빼주고 3번째 위치에서 8을 넣을 수 있게 다음 반복으로 넘어가는 구조가 됩니다.

N과 M (2)