꾸준히 개발하기

백트래킹 복습 겸 같은 문제 다른 유형을 풀어봤다.

사실 로직 자체는 그냥 N과 M 문제와 똑같다. 다만 여기에서 이제 수열이 오름차순 정렬이 되어서 출력이 되어야 한다는 조건만 하나 붙어 있을 뿐! 그래서 sorted() 함수를 사용해서 정렬해준 뒤 그 결과가 answer에 없으면 넣어주는 코드를 추가했다.

아 그리고 숫자로 이루어진 리스트의 경우 바로 join해주면 int형이라 에러가 난다. 각각의 요소를 str으로 바꿔주는 map함수 잊지말고 적용해주자~!

코드는 다음과 같다.

n, m = map(int, input().split())


result = []

answer = []


def back():
    if len(result) == m:
        tmp = sorted(result)
        if tmp not in answer:
            answer.append(tmp)
        return

    for i in range(1, n + 1):
        if i not in result:
            result.append(i)
            back()
            result.pop()


back()

for i in answer:
    print(" ".join(map(str, i)))

10.7부터 week1을 달리고 있다.

https://www.acmicpc.net/workbook/view/8997

백준 15649 N과 M (1)

N과 M문제는 자다가도 풀 수 있어야 한다고 해서 순열로 풀었다가 눈물 좍좍 흘리면서 백트래킹을 뿌셨다.

백트래킹은 불필요한 경우를 탐색하지 않는다. 즉 특정 조건에서는 탐색을 그만하고 뒤로 되돌아가는(back) 성질을 가지고 있다. 따라서 DFS로 무작정 들이박으면 시간초과가 나는 상황에 유용하게 쓰이겠다.

숫자 1~N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제이다.

따라서 1) 수열의 길이가 M을 넘으면 안됨 2) 배열 내에 중복 X 두 가지 조건을 만족하는 숫자 뽑기를 진행하면 된다.

ex. N = 4, M = 3

1. 첫번째 숫자로 1,2,3,4 중 가장 작은 숫자인 1을 선택한다. -> for 문으로 순차 증가
2. 두번째 숫자로 2,3,4 중 가장 작은 숫자인 2를 선택한다. -> 선택 과정에서 배열 안에 존재하는지 체크하여 중복 제거
3. 세번째 숫자로 3,4 중 가장 작은 숫자인 3을 선택한다.
4. 수열의 길이가 M(3)이 되었으므로 다시 단계 3로 돌아간다. -> 재귀 탈출
5. 세번째 숫자로 4를 고른다. 
6. 수열의 길이가 M(3)이 되었으므로 단계 2로 돌아간다.
7. 두번째 숫자로 다음 작은 숫자인 3를 선택한다.
8. 세번째 숫자로 2,3,4 중 2를 선택한다. -> 추후 여기에서 다시 숫자를 고를 때 3은 이미 배열안에 존재하므로 X
9. ... 반복

즉 위의 과정을 코드로 구현하면 다음과 같다. 

n, m = map(int, input().split())
result = []

def backTracking():
    # 수열의 길이가 m이면 출력해주고 전단계로 돌아가기 (재귀 탈출)
    if len(result) == m:
        print(" ".join(map(str, result)))  # "구분자".join(리스트)
        return
    # 1 ~ n 까지 체크
    for i in range(1, n + 1):
        # 중복 체크
        if i not in result:
            result.append(i)
            backTracking()
            # return 문으로 돌아온 경우 실행되는 부분
            result.pop()  # n=4, m=3일때 1,2,3이 들어온 경우 3을 없앰으로써 전단계로 돌아감


backTracking()

백트래킹 어렵다. 재귀라서 더 어렵게 느끼는 것 같기도 하고...! 익숙해질때까지 킵고잉이다 정말

출력 관련해서 문자열 다룰 때 자주 쓰이는 함수 join도 짚고 가보자.

"구분자".join(리스트) 형태로 사용하며 join 함수는 매개변수로 들어온 리스트에 있는 요소 하나 하나를 합쳐서 하나의 문자열로 바꿔 반환하는 함수이다. "구분자"를 값과 값 사이에 넣어서 하나의 문자열로 합쳐준다!

파이썬이 문자열 다룰 때 깡패인 언어인 만큼 join함수에도 익숙해지자. 자주 써야된다~!