[BOJ/백준] N과 M (1~8) (Python 파이썬) [15649, 15650, 15651, 15652, 15654, 15655, 15656, 15657]

https://www.acmicpc.net/problemset?search=N%EA%B3%BC+M 

문제 - 검색 결과: N과 M

BackTracking 유형의 N과 M 문제입니다. 버전이 총 12개인데, 이 중 2~3개만 풀으셔도 무방할 것 같습니다.

이전에 풀이를 진행했던 N-Queen 문제의 포스팅을 보고 오시면 BackTracking 유형에 대해서 이해하실 수 있을 겁니다. 

2022.08.10 - [Algorithm/BackTracking] - [BOJ/백준] 9663번 N-Queen (Python/파이썬)

[BOJ/백준] 9663번 N-Queen (Python/파이썬)

문제 번호가 올라갈수록 제약 조건이 추가되는데, 가장 간단한 Backtracking부터 풀어보면서 어떻게 제약 조건을 통해서 가지치기를 진행하는지 살펴보고 점차 제약 조건을 발전시켜 가면서 Backtracking 유형에 익숙해지도록 연습하면 좋을 듯합니다.

---

N과 M (1) 15649번

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

15649번: N과 M (1)

이 중에서 가장 기초가 되는 N과 M(1) 15649번 문제를 먼저 살펴보겠습니다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	65212	40568	26935	61.458%

 

문제

자연수 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

---

 

이번에도 같은 흐름을 적용해서 풀이해 보겠습니다.

1. 가장 먼저 탐색의 종료 조건을 확인
2. 반복문 내에서 제약 조건을 검사하여 가지 치기를 진행
3. 모든 경우의 수를 검토하기 위해서  각 후보군에 대해서
    append()
    DFS(depth + 1)
    pop() 형식으로 백트래킹을 구현

 

N-Queen 문제에서는 제약 조건이 꽤나 복잡했지만, 해당 문제에서는 제약 조건이 단순하게
"방문했던 수는 다시 방문하지 않는다"로 정리됩니다. 따라서 따로 promising 함수를 만들 필요 없이 중복 체크만 수행합니다.
State Space Tree에서는 이전에 방문했던 수에 대해서는 가지치기를 진행하는 것이죠.
위 두 내용은 조건문 한 줄로 표현가능합니다.

 

n, m = list(map(int, input().split()))
ans = []
def dfs():
    if len(ans) == m:  # m개까지 채우고 출력, 이후 백트래킹
        print(' '.join(map(str, ans)))
        return

    for i in range(1, n+1):
        if i not in ans: # 검사
            ans.append(i)
            dfs()
            ans.pop()
dfs()

 

 

---

N과 M (2) 15650

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

15650번: N과 M (2)

 

문제

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

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

 

입력

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

 

출력

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

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

 

 

---

이전 문제에 "오름 차순" 조건이 추가되었습니다.
이를 구현하기 위해서 출력을 위해 자연수를 담아두는 ans에 항상 오름차순으로 값이 담기도록 보장하면 됩니다.
즉, 지금 삽입하려는 수가 ans의 가장 큰 수보다 크면 삽입이 가능한 겁니다. 만약 작다면 가지치기를 진행하는 것이죠.

이때, ans에 맨 처음 값을 넣을 때는 비교할 대상이 없기 때문에 이 경우에 대해서만 분기 처리를 진행해야 합니다.

n, m = list(map(int, input().split()))
ans = []
def dfs():
    if len(ans) == m:  # m개까지 채우고 출력, 이후 백트래킹
        print(' '.join(map(str, ans)))
        return

    for i in range(1, n+1):
        if i not in ans:
            if len(ans) == 0:
                ans.append(i)
                dfs()
                ans.pop()
            else:
                if i > ans[-1]: # 오름차순
                    ans.append(i)
                    dfs()
                    ans.pop()
dfs()

 

 

---

N과 M (3) 15651번

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

15651번: N과 M (3)

 

문제

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

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

 

입력

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

 

출력

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

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

---

같은 수를 여러 번 골라도 된다는 조건이 생겼습니다. 이것이 무엇을 의미할까요?
이전 문제들에서는 "중복이 되면 안된다", "오름 차순이어야 한다"와 같은 제약 조건을 설정해서 해당 조건에 맞지 않는다면 가지치기를 진행하여 그 방향으로는 탐색을 진행하지 않았습니다.

하지만 이 경우에는, 제약 조건이 사라진 것과 같고 즉, 가지치기를 진행하지 않는 것과 같습니다.
쉬운 문제이지만 제약 조건을 설정하여 가지치기를 진행함으로써 후보군을 줄여가는 BackTracking 기법을 잘 이해했다면 위와 같이 연결 지을 수 있습니다.

트리로 표현하면 가지치기없이 모든 경우의 수를 반영한 트리가 그려질 것입니다.

n, m = list(map(int, input().split()))
ans = []
def dfs():
    if len(ans) == m:  # m개까지 채우고 출력, 이후 백트래킹
        print(' '.join(map(str, ans)))
        return

    for i in range(1, n+1): # 제약 조건 없음
        ans.append(i)
        dfs()
        ans.pop()
dfs()

 

 

---

N과 M (4) 15652번

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

15652번: N과 M (4)

 

문제

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

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

 

입력

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

 

출력

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

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

---

이번에는 "비내림차순"이라는 조건이 추가되었습니다.
즉, 같은 수를 여러 번 고르는 것은 허용하되, 내림차순이 되어서는 안됩니다.

그럼 우선은 (1) 중복 체크는 없애고 (2) 삽입하려는 수가 ans의 가장 큰 수보다 크거나 같으면 됩니다.

n, m = list(map(int, input().split()))
ans = []
def dfs():
    if len(ans) == m:  # m개까지 채우고 출력, 이후 백트래킹
        print(' '.join(map(str, ans)))
        return

    for i in range(1, n+1): #중복 체크 실시 xx
        if len(ans) == 0:
            ans.append(i)
            dfs()
            ans.pop()
        else:
            if i >= ans[-1]: # 비내림차순
                ans.append(i)
                dfs()
                ans.pop()
dfs()

 

 

---

이 후 N과 M 5,6,7,8 문제는 1부터 N까지의 자연수를 가지고 수열을 만드는 것이 아니라 입력 받은 임의의 수열을 가지고 문제를 진행할 뿐, Backtracking의 핵심 코드는 동일하기 때문에 생략하겠습니다.

해당 포스팅을 통해서 N과 M 문제를 잘 따라오셨다면 앞으로 다른 문제를 푸실 때는
제약조건을 어떻게 설정할 지, 가지치기와 탐색을 어떻게 실시할 지에 대한 고민을 하셔서 적용하시면 됩니다.