[BOJ] 15650 - N과 M(2)

풀어보기

접근

1부터 N까지의 수 중 M개를 고른 수열을 오름차순으로 출력해야 한다.

우선 재귀를 통해 풀 수 있겠다는 생각이 들었다. 그리고 간만에 구현해보는 DFS에 정신이 아득해질 무렵 작동하는 코드를 만들어낼 수 있었다(...).

코드

from sys import stdin

N, M = tuple(int(i) for i in stdin.readline().split())

def search(answer, depth, next_idx):
    global N, M

    if depth == M:
        print(" ".join(answer))
        return

    for i in range(next_idx, N + 1):
        answer += str(i)
        search(answer, depth + 1, i + 1)
        answer.pop()

search([], 0, 1)

일반적인 DFS에서 쓰는 방문 여부 배열은 이 문제에서는 쓸 필요가 없었다. 원 데이터가 사전순으로 이미 정렬되어 있어 다음 탐색 범위를 조정하는 것 만으로 중복 탐색을 방지할 수 있기 때문이라 할 수 있다.

백트래킹 문제는 아직 많이 풀어보지 않아서 그런건지, 이것과 DFS의 차이점이 무엇인지 의문이 들어 좀 알아보았다. 구현만 보면 사실상 똑같지만 문제 풀이 전략 수립시 관점이 약간 다른 것 같다. 호주를 오스트레일리아라고도 부르는 것과 비슷한 느낌이라 해야 할까?...