[BOJ / 파이썬] 15649: N과 M (1)

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

단계 : 백트래킹

알고리즘 분류 : 백트래킹

 

풀이:

숫자 두개 n, m을 받아서 1~n까지의 수 중 중복 없이 m개를 골라야한다.

n, m이 정해져 있다면 일반적인 반복문으로 처리할 수 있겠지만 정해져 있기 때문에 다른 방법을 써야한다. 사실 n, m이 정해져 있어도 수가 크면 반복문으로 하기 어렵다.

 

문제 분류가 백트래킹이라고 하는데 백트래킹을 구글에 검색하면 해를 구하는 도중 해가 아니어서 막히면 막히기 전으로 다시 돌아가서 해를 찾는 기법이라고 말하는데 정확히 설명해달라고 한다면 솔직히 잘 할 자신은 없다.

 

다시 문제 내용으로 돌아와서 풀이를 설명하겠다.

 

먼저 중복을 방지하기 위해 방문 여부를 알려주는 visited라는 리스트를 만들어서 숫자의 범위인 n만큼 False라는 값을 채워준다. 또한 결과를 담아서 출력해줄 result라는 빈 리스트를 선언해준다.

 

함수는 d, n, m이라는 인자를 받아 실행되는데 d는 현재 result에 담긴 숫자의 개수이고 n과 m은 문제의 n과 m과 같다. d가 m과 같으면 문제에서 요구하는 수열을 찾은 것이므로 출력을 해주고 함수를 종료해준다. 이때 result 리스트에 담긴 것은 int형이어서 map 함수를 이용해 result 내부의 값들을 str 값으로 변환하여 .join 메서드를 이용하였다.

 

d가 m과 같지 않다면 아직 해당하는 숫자를 더 찾아야 한다. n 범위 내에 있는 숫자들을 보며 visited에 False값이 저장돼 있는 숫자는 아직 방문하지 않은 것이니 result에 해당 숫자를 넣어주고(i는 인덱스니까 숫자는 i+1) 해당 숫자를 방문함으로 표시를 바꿔준다(visited[i] = True). 그 다음 d값을 1을 증가시켜 함수를 다시 실행하면 두번째 실행된 함수는 방금 넣은 숫자를 result에 가지고 그 숫자를 방문했다고 표시한 상태로 넘어갈 수 있다. 그 과정을 반복하다가 해당 함수에서 나오게 되면 방문했다는 표시를 다시 False로 고쳐주고 넣었던 숫자를 빼줘야 한다. 그렇게 된다면 아래 사진처럼 모든 경우의 수를 확인할 수 있게된다.

 

 

코드

import sys


def solve(d, n, m):
    if d == m:
        print(" ".join(map(str, result)))
        return
    for i in range(n):
        if visited[i] == False:
            visited[i] = True
            result.append(i + 1)
            solve(d + 1, n, m)
            visited[i] = False
            result.pop()


n, m = map(int, sys.stdin.readline().split())

visited = [False] * n
result = []
solve(0, n, m)