[Python] N과 M(1) (백준 15649번 파이썬)

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

15649번: N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

 

백트래킹 알고리즘 문제입니다.

그동안 백트래킹 문제를 계속 피해왔었는데, 슬슬 공부할 때가 됐다 싶어서 개념을 잡고 있습니다.

기본적으로는 DFS와 같이 모든 경우의 수를 탐색하지만, 조건에 따라 유망(Promising)한 노드에 대해서 방문하고 유망하지 않은 노드는 탐색을 중지합니다. 이를 가지치기라고 하며, 이전 노드로 돌아가서 다른 경우에 대해서 탐색을 이어갑니다.

 

아래의 이미지 속 그래프 그림과 같이 모든 경우의 수를 탐색하되, 조건에 따라 탐색을 중지하고 이전 노드로 돌아와 다른 경우를 탐색한다고 생각하면 이해가 쉬울 것 같습니다.

아이디어는 금방 이해하더라도, 이를 코드로 구현하기 위한 과정이 조금 힘들었습니다.

 

 

코드

#백준 15649 n과 m
#1부터 n까지의 자연수 중에서 중복 없이 m개를 고른 수열
def func():
    if len(s) == m: #자릿수가 다 찼으면 return 해서 부모노드로 돌아감
        print(' '.join(map(str, s)))
        return
    for i in range(1,n+1): #자릿수가 아직 안찼으면
        if visited[i] == True: #이미 사용한 수는 건너뜀(1 썼으면 다음 2, 2도 썼으면 다음 3)
            continue
        visited[i] = True #수 사용처리
        s.append(i) #수열에 수 넣음
        func()
        s.pop()
        visited[i] = False #방금 사용한 수 빼기

n,m = map(int, input().split())
s = []
visited = [False]*(n+1)
func()

 

 

수열을 담기 위한 배열 s를 생성하고, 1부터 n까지의 수를 사용했는지를 체크하기 위해 visited 배열을 만들었습니다.

(배열 명은 BFS나 DFS사용하던 그대로 그냥 visited라고 명명했습니다.)

 

func() 함수를 실행해 백트래킹을 진행합니다.

 

if len(s) == m: #자릿수가 다 찼으면 return 해서 부모노드로 돌아감
        print(' '.join(map(str, s)))
        return

이 부분은 s에 담긴 수열의 갯수가 m과 같은지, 즉 정해진 자릿수가 다 찼는지를 체크하는 부분입니다.

만약 4개를 고르는데 이미 4개의 수가 다 뽑혔다면, 조건에 만족하므로 탐색을 종료합니다.

(실제 실행시엔 여기서 return 된 후 이전 노드, 즉 m이 4일 때는 세번째 자리가 다 찬 상태로 돌아갑니다.)

 

 

for i in range(1,n+1): #자릿수가 아직 안찼으면
        if visited[i] == True: #이미 사용한 수는 건너뜀(1 썼으면 다음 2, 2도 썼으면 다음 3)
            continue
        visited[i] = True #수 사용처리
        s.append(i) #수열에 수 넣음
        func()
        s.pop()
        visited[i] = False #방금 사용한 수 빼기

1부터 n까지의 수를 각 자릿수에 넣는 부분입니다.

아직 자릿수가 다 안찬 경우, i가 1일때 사용처리를 해주고 배열s에 1을 넣습니다. 그리고 다음 자릿수의 숫자를 넣기 위해 한번더 함수를 실행합니다.

자릿수가 다 차서 return되면 배열s를 비워주고, 방금 사용한 수를 다시 사용할 수 있도록 False로 변경합니다.

 

 

백트래킹 문제를 처음 풀어봐서 어렵게 느껴졌는데, 앞으로 계속 연습하면서 실력을 늘려나가야 될 것 같습니다.