백준 문제 중 15650번 15651번, 백트래킹, ‘N과 M(3), N과 M(4)’

백트래킹에 있는 N과 M 시리즈 몇개를 한번에 다루려고 한다.

N 과 M (2) 풀이

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

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

1~n까지 수를 각각 노드로 dfs하되 discovered 배열을 두어 이미 방문했다면 생략하고, discovered의 길이가 m이되면 종료 하게끔 설정을 했다.

주의 할 점은 두가지 정도가 있다.

1. 자식 노드들 사이의 탐색을 모두 하기 위해 discoverd 에 1번 자식 노드를 추가하고 dfs를 한뒤 dfs 가 종료된다면 1번 자식 노드를 삭제하고 그 다음 2번자식이 시작 되게끔 해야한다.

2. 중복을 제거하기 위해서 dfs를 실시 하는 범위를 중복이 안생기게끔 적절하게 줄여 나가야한다.

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

 # 방문한 노드를 표시할 배열 선언
discovered = []

def dfs(idx):

     # 방문 배열의 크기가 m이 된다면 출력 하고 return으로 재귀 종료
    if len(discovered)==m:
        print(*discovered)
        return

     # idx를 스캔의 시작점 설정하여 이전 depth에서 추가된 원소의 다음의 원소부터 스캔을 시작한다.
    for i in range(idx,n+1):
        if i not in discovered:
            discovered.append(i)
            dfs(i+1)
            discovered.pop()

dfs(1)

4 4
1 2 3 4

N 과 M (3) 풀이

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

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

N 과 M (1)와 다르게 중복이 가능함으로 discovered 에 해당 노드가 있는지 판단하는 조건을 없애면 된다.

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

discovered=[]

def dfs():

    if len(discovered)==m:
        print(*discovered)
        return

    for i in range(1,n+1):
        discovered.append(i)
        dfs()
        discovered.pop()

dfs()

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

N 과 M (4)

위에 있는 N 과 M (2)와 다르게 중복이 가능함으로 discovered 에 해당 노드가 있는지 판단하는 조건을 없애면 된다.

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

discovered=[]
def dfs(start):

    if len(discovered)==m:
        print(*discovered)
        return
    
    for i in range(start,n+1):
        discovered.append(i)
        dfs(i)
        discovered.pop()

dfs(1)

3 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3