[백준 백트래킹] N과 M 시리즈(1~12)

백트래킹은 DFS의 일종이라고 하지만, 조금 다르다!

우선 DFS는 가능한 모든 경로를 깊이 우선으로 탐색하는 것이다. 

반면에, 백트래킹은 불필요한 경로는 굳이 탐색하지 않고, 탐색할 필요가 없다고 판단하면 끝까지 탐색하지 않는 것이다.

둘 다 일반적으로는 재귀 함수로 구현한다.

 

 백준의 대표적인 백트래킹 연습 문제인 N과 M 시리즈를 모두 풀어보았다.

 

1.

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

15649번: N과 M (1)

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

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

import sys
from itertools import permutations

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

# itertools permutaions으로 풀어내는 경우
# nlist=list(range(1,n+1))
# perm=list(permutations(nlist,m))
#
# for p in perm:
#     print(*p, sep=' ')

# dfs를 이용한 백트래킹으로 풀어내는 경우
visited=[0]*(n+1)
arr=[0]*(m)
def dfs(cnt):
    if cnt==m:
        print(*arr, sep=' ')
        return
    for i in range(1,n+1):
        # 아직 방문하지 않은 수인 경우
        if visited[i]==0:
            visited[i]=1
            arr[cnt]=i
            dfs(cnt+1)
            visited[i]=0

dfs(0)

1부터 N까지의 자연수 중 중복없이 M개를 선택하는 경우이고, 뽑는 순서가 다르면 다른 경우의 수로 간주하기 때문에 ('1 4'!='4 1')

순열을 생각해서 itertools의 permutations로 간단하게 풀 수 있다.

하지만, 백트래킹을 이용해서 풀기로 했기 때문에 DFS를 이용한 백트래킹으로 문제를 풀었다.

 

DFS로 순열/조합을 구현했던 방식과 비슷하다. cnt 변수를 이용해서 현재 까지 고른 수의 개수를 카운팅해주고, cnt 변수가 m이 되면 m개 만큼 수를 골랐다는 뜻이므로 arr에 저장해둔 경우의 수를 출력해준다.

아직 cnt 변수를 채우지 못해 수를 더 뽑아야 하는 상황이라면 for 문 탐색을 통해 아직 방문하지 않은 수를 찾고, 해당 수를 방문처리 해준 뒤 현재 arr[cnt](1을 고르고, 4를 고른 경우라면 arr[0]=1, arr[1]=4,..)에 현재 수를 할당해주고, cnt+1을 넘겨준 DFS 재귀 탐색을 반복한다. 

해당 재귀 탐색이 끝나면 방문 처리해줬던 수를 다시 방문하지 않은 수로 처리해주고, 다시 for문을 탐색하면서 선택할 수 있는 다음 수를 찾는다.

 

다음 N과 M 시리즈 문제의 조건에 따라 조금씩 변형될 뿐, 이와 같은 형식이 반복된다.

 

 

 

2.

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

15650번: N과 M (2)

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

import sys

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

# 1~n 까지의 자연수 중 m개를 고른 수열, 고른 수열은 오름차순이어야 함
visited=[0]*(n+1)
arr=[0]*(m)
def dfs(cnt, num):
    if cnt==m:
        print(*arr, sep=' ')
        return
    for i in range(num+1, n+1):
        if visited[i]==0:
            visited[i]=1
            arr[cnt]=i
            dfs(cnt+1, i)
            visited[i]=0

dfs(0,0)

1번 시리즈와 달리, 고른 수열이 오름차순이어야 하므로 이미 고른 수보다 큰 수만을 선택할 수 있도록 for문 탐색의 범위를 range(1, n+1)이 아니라, 선택 후 dfs의 매개 변수로 넘어온 num 값보다 +1인 수부터 n+1까지 탐색하는 것으로 변경해주면 된다.(range(num+1, n+1))

 

 

 

3.

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

15651번: N과 M (3)

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

import sys

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

arr=[0]*m
def dfs(cnt):
    if cnt==m:
        print(*arr,sep=' ')
        return
    for i in range(1,n+1):
        arr[cnt]=i
        dfs(cnt+1)

dfs(0)

1번 시리즈와 비교했을 때, 같은 수를 여러 번 골라도 된다는 점이 다르다! 즉, 이미 뽑은 수를 또 뽑아도 된다는 것이다.

그러므로 이미 뽑은 수인지 확인했던 visited 배열이 필요 없어진다.

 

 

 

4.

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

15652번: N과 M (4)

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

import sys

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

arr=[0]*m
def dfs(cnt, num):
    if cnt==m:
        print(*arr,sep=' ')
        return

    for i in range(num,n+1):
        arr[cnt]=i
        dfs(cnt+1, i)

dfs(0,1)

3번 시리즈와 비교했을 때 같은 수를 여러 번 뽑아도 된다는 것은 동일하지만, 이번엔 이미 뽑은 수보다 같거나 큰 경우에만 선택할 수 있다.

그래서 dfs 안에 for문을 range(num, n+1)로 선언해서 현재 수부터 n까지만 선택할 수 있도록 제한한다.

 

 

 

5.

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

15654번: N과 M (5)

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

• N개의 자연수 중에서 M개를 고른 수열

import sys

n,m=map(int, sys.stdin.readline().split(' '))
nlist=list(map(int, sys.stdin.readline().split(' ')))
nlist.sort()

visited=[0]*(n)
arr=[0]*(m)
def dfs(cnt):
    if cnt==m:
        print(*arr, sep=' ')
        return

    for i in range(n):
        if visited[i]==0:
            arr[cnt]=nlist[i]
            visited[i]=1
            dfs(cnt+1)
            visited[i]=0

dfs(0)

5번부터는 1부터 N까지의 수 중 M개를 뽑는 게 아니라, 입력으로 제시된 N개의 수 중 M개를 뽑는 것이다!

nlist 배열에 N개의 수를 입력받아 저장하고, 사전순으로 출력해야 되기 때문에 nlist를 오름차순 정렬해준다.

• 1~4번까지는 1부터 n까지 순차적으로 탐색하므로, 정렬이 필요없었지만 정렬되지 않은 수열을 입력받는 5번부터는 정렬이 필요하다.

지금까지 풀어왔던 방식과 같이 arr[cnt]에 nlist[i]를 저장해주고 해당 인덱스에 방문했다고 visited 배열을 1로 갱신해준 뒤에 dfs 탐색을 통해서 cnt의 개수가 m이 되면 arr를 출력하는 방식을 반복한다.

 

 

 

6.

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

15655번: N과 M (6)

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

import sys

n,m=map(int, sys.stdin.readline().split(' '))
nlist=list(map(int, sys.stdin.readline().split(' ')))
nlist.sort()

visited=[0]*n
arr=[0]*m
def dfs(cnt,num):
    if cnt==m:
        print(*arr, sep=' ')
        return

    for i in range(num+1, n):
        if visited[i]==0:
            arr[cnt]=nlist[i]
            visited[i]=1
            dfs(cnt+1, i)
            visited[i]=0

dfs(0,-1)

5번과 비교했을 때 선택한 수열이 오름차순이어야 하므로 앞서 사용했던 방식대로 nlist를 정렬해준 뒤에 이미 선택한 인덱스보다 큰 경우에만 for문 탐색을 할 수 있도록 range(num+1, n)으로 설정해준다.

 

 

7. 

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

15656번: N과 M (7)

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

import sys

n,m=map(int, sys.stdin.readline().split(' '))
nlist=list(map(int, sys.stdin.readline().split(' ')))
nlist.sort()

arr=[0]*m
def dfs(cnt):
    if cnt==m:
        print(*arr, sep=' ')
        return

    for i in range(n):
        arr[cnt]=nlist[i]
        dfs(cnt+1)

dfs(0)

5번과 달리 이미 선택한 수를 또 선택할 수 있으므로 visited 배열이 필요없어졌다.

 

 

8.

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

15657번: N과 M (8)

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

import sys

n,m=map(int, sys.stdin.readline().split(' '))
nlist=list(map(int, sys.stdin.readline().split(' ')))
nlist.sort()
arr=[0]*m
def dfs(cnt, num):
    if cnt==m:
        print(*arr, sep=' ')
        return
    for i in range(num, n):
        arr[cnt]=nlist[i]
        dfs(cnt+1, i)

dfs(0,0)

7번과 달리, 고른 수열이 비내림차순이어야 하므로, for문 탐색의 범위를 range(num, n)으로 설정해준다.

 

9.

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

15663번: N과 M (9)

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

• N개의 자연수 중에서 M개를 고른 수열

import sys

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

nlist=list(map(int, sys.stdin.readline().split(' ')))

visited=[0]*n
arr=[0]*m
ans=set()
def dfs(cnt):
    if cnt==m:
        ans.add(' '.join(map(str,arr)))
        return
    for i in range(n):
        if visited[i]==0:
            visited[i]=1
            arr[cnt]=nlist[i]
            dfs(cnt+1)
            visited[i]=0

dfs(0)

for s in sorted(ans,key=lambda x:list(map(int,x.split(' ')))):
    print(s)

이전까지 풀었던 문제들과 달리 입력되는 N개의 자연수 중 중복되는 수가 존재한다.

예를 들어, 1 7 9 9와 같은 자연수들이 입력되는 것이다!

이전과 같이 풀이하면 9가 두 개이므로 1 9, 1 9와 같이 위치는 다르지만 결과는 똑같은 경우의 수가 나오는 것이다.

 

이러한 경우의 수의 중복을 제거해주기 위해서 cnt가 m개가 되면 arr를 문자열 형태로 변경하여 ans set에 추가해주면서 중복을 제거해준다.

그리고 set 자료형은 데이터의 순서가 없기 때문에 정렬을 해서 출력해줘야 하는데, 문자열을 기준으로 정렬해주면 정수 기준으로 정렬되길 원하는 문제의 조건에 부합하지 않는다. ('9 10', '10 9'라는 원소가 존재할 경우 문자열을 기준으로 정렬해주면 '10 9'가 먼저 와버린다.)

그래서 sorted 함수에 key로 원소를 정수 배열로 변경해준 값을 기준으로 정렬해줄 수 있도록 x:list(map(int, x.split(' ')))를 lambda 값으로 할당한다.

 

 

 

10. 

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

15664번: N과 M (10)

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

import sys
input=sys.stdin.readline
n,m=map(int, input().split(' '))
nlist=list(map(int, input().split(' ')))
nlist.sort()

visited=[0]*n
arr=[0]*m
ans=set()
def dfs(cnt, num):
    if cnt==m:
        ans.add(' '.join(map(str, arr)))
        return

    for i in range(num+1,n):
        if visited[i]==0:
            visited[i]=1
            arr[cnt]=nlist[i]
            dfs(cnt+1, i)
            visited[i]=0

dfs(0,-1)

for s in sorted(ans, key=lambda x:list(map(int, x.split(' ')))):
    print(s)

9번과 달리 비내림차순으로 수를 뽑아야 하므로, nlist를 정렬해주고, for문의 범위를 range(num+1, n)으로 설정해준다.

 

 

 

11.

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

15665번: N과 M (11)

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

import sys

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

arr=[0]*m
ans=set()
def dfs(cnt):
    if cnt==m:
        ans.add(' '.join(map(str,arr)))
        return

    for i in range(n):
        arr[cnt]=nlist[i]
        dfs(cnt+1)

dfs(0)

for s in sorted(ans, key=lambda x:list(map(int, x.split(' ')))):
    print(s)

9번과 달리, 같은 수를 여러 번 뽑아도 되므로, visited 배열이 필요없어진다.

 

 

 

12.

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

15666번: N과 M (12)

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

import sys

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

nlist.sort()

arr=[0]*m
ans=set()
def dfs(cnt, num):
    if cnt==m:
        ans.add(' '.join(map(str, arr)))
        return

    for i in range(num, n):
        arr[cnt]=nlist[i]
        dfs(cnt+1, i)

dfs(0,0)

for s in sorted(ans, key=lambda x:list(map(int, x.split(' ')))):
    print(s)

11번과 달리, 비내림차순으로 수를 뽑아햐 하므로 nlist를 정렬해주고 for문의 범위를 range(num, n)으로 설정한다.

 

 

 

 

위 문제들은 DFS 반복을 통해 가능한 모든 경우의 수를 탐색하지만, cnt의 값이 뽑고자 하는 수인 m만큼이면 더 이상 탐색하지 않고 return한다는 점에서 백트래킹을 연습하기에 좋은 문제들이다!

또, 순열/조합을 itertools의 combinations/permutations를 사용하지 않고 직접 구현하는 방법을 충분히 연습할 수 있었던 것 같다.