[BOJ][Python]15654번 풀이

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

import sys
ssr = sys.stdin.readline

def sol(num_len):
    if num_len == m:
        print(*ans)
        return
    for i in range(n):
        if visited[i] == 1:
            continue
        visited[i] = 1
        ans.append(num[i])
        sol(num_len + 1)
        ans.pop()
        visited[i] = 0
    return

n,m = map(int, ssr().split())
num = list(map(int, ssr().split()))
visited = [0 for _ in range(n)]
num.sort()
for i in range(n):
    ans = [num[i]]
    visited[i] = 1
    sol(1)
    visited[i] = 0

오랜만에 푸는 백트래킹 문제입니다. 저는 백준을 풀면서 정말 큰 벽에 막혔다는 생각을 두 번 했었는데 첫번째는 재귀이고, 두번째는 백트래킹입니다. 아무런 이론도 확립이 되지 않은채 백준 문제만으로 알고리즘 공부를 한다는 건 어떻게 보면 상당히 미련한 짓입니다. 마치 수학 공부를 하겠다고 하면서 아무런 지식도 없는채로 미분적분학을 집어드는 것 같은 느낌이죠. 처음에는 몰라도 풀 수 있는 문제들이 나오다가 챕터가 진행될수록 이론적 배경이 없으면 어떻게 해야하는지도 모르겠는 문제들이 나오기 시작합니다.

 

저한테는 재귀가 그랬고, 백트래킹이 그랬습니다. 입출력이니 사칙연산이니 조건문 등등... 모르더라도 추론만 할 줄 알면 풀 수 있는 문제들이 나오다가 어느 순간 부터 직관성이 떨어지는 코드가 나오고, 풀이를 봐도 모르겠고 기본적인 이론도 모르니 풀 수 있을리가 없죠. 그게 어느덧 1년 남짓 된 일 입니다. 같이 졸업작품을 진행했던 친구도 독학으로 알고리즘 공부를 하던 친구였기에 이것저것 많이 물어봤었지만 제가 잘 모르니까 설명의 대부분을 이해를 못했었고, 나중에는 미안하니까 물어보기도 힘들어졌어요. 그리고 제 기억으로는 n과m(1)이 제가 그 친구에게 마지막으로 물어봤던 백준 문제였습니다.

 

어떻게든 이해해보려고 했었지만 한 70퍼센트 정도밖에 이해하지 못했던 것 같아요. 그 뒤는 친구랑 같이 짰던 코드를 조금씩 변경해가면서 뒤에 나오는 문제들에 적용을 시키는 작업을 했었죠. 이해는 다 못했으니 그냥 결과값을 보면서 조금 손보는 일을 반복했었습니다. 그랬던 시절이 있었는데 이제는 이 정도 문제는 대충 보면 푸는 방법이 생각나게 되었네요. 사실 백준 문제를 잘 푼다고 그 사람이 알고리즘에 통달을 했고 프로그래밍을 잘한다고 말할 수는 없습니다. 대학생분들은 공감하실텐데 학점이 좋다고 해서 팀프로젝트를 진행할 때 해당 인원의 실력이 좋지만은 않거든요. 오늘도 사설이 길었습니다. 아무튼 이젠 혼자서도 잘풀게 되어서 기분이 좋다는 얘기입니다.

 

문제 접근은 기본적인 백트래킹입니다. 해당 문제의 경우 중복되는 숫자를 뽑을 수 없기 때문에 방문 처리를 해줘야하구요, 사전 순으로 증가해야한다고 하니 오름차순 정렬을 해주면 좋겠네요. 그 다음부터는 기본적인 백트래킹과 동일합니다. 먼저 리스트에 처음 시작하는 값을 넣습니다. 굳이 안넣어도 상관이 없기는 합니다. sol에서 이중 반복문으로 작성하면 오히려 더 직관적일 것 같아요.

 

sol에서는 ans의 길이를 재고 그게 m과 같다면 ans를 출력합니다(len(ans)로 해도 상관없을 것 같아요). 조건문에 해당이 되지 않을 때는 반복문으로 조합을 만들어줍니다. 여기서도 반복되는 숫자를 뽑지 않기 위해서 방문처리를 해주셔야합니다. 이미 방문했던 원소라면 continue로 넘어가줍시다. return을 하면 원소가 모자라서 출력을 못하게 되니까 넘어만 갑시다. 그렇게 방문하지 않은 원소는 추가하고 재귀 호출을 진행하다보면 길이가 m과 같아지는 일이 생기겠죠. 그 이후에 pop을 통해서 원소를 빼주는 과정이 필요합니다. 안그러면 한 번만 출력하고 전부 continue로 스킵해버리겠죠. 그래서 마지막에 들어간 원소를 빼고 방문 처리 또한 수정을 해주시면 됩니다.

 

마지막 정리도 할 겸 예시를 들어보면 긴 꼬챙이에 서로 다른 재료를 중복 하지 않고 꽂을 수 있는 경우를 모두 보이는 것과 동일하다고 할 수 있을 것 같습니다. 물론 우리는 눈으로 보니까 방문 처리를 안해도 아 뭐가 없구나 하고 바로 알겠지만 컴퓨터는 아니니까 방문 처리는 컴퓨터를 위해 해주는 작업이라고 생각하시고, 그 이외에는 똑같죠. 마치 명절에 산적꼬치를 만들듯이 말이에요. 맛살을 꽂았다면 해당 꼬치에는 더 이상 맛살을 꽂지 않고 햄, 파, 당근 등등 다른 재료들을 꽂으니까요. 다음 꼬치를 만들 때는 순서를 또 좀 바꿔서 만드는, 그런 일상 생활의 모습과 닮아있는 문제라고 해도 될 것 같습니다.