[Python][백준] 15650. N과 M (2) / 백트래킹(S2)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

N,M = map(int,input().split())
visited = [0] * (N+1)
rs = []


def dfs(n,lst):
    if n >= M :
        if sorted(lst) not in rs:
            rs.append(lst[:])
        return 

    for i in range(1,N+1):
        if visited[i] ==0:
            visited[i] = 1
            lst.append(i)
            dfs(n+1,lst)
            visited[i] = 0
            lst.pop()

dfs(0,[])

for r in rs:
    print(*r)

 

1. dfs의 백트래킹 정석대로 풀어보았다. 

 

2. 먼저 방문 리스트를 만들어주고, 방문하지 않은 값들을  append 한다.

 

3. 그리고 dfs를 다시 호출에 매개변수로 n+1 (깊이)와 갱신된 lst를 준다.

 

4. 다음  dfs의 호출을 위해 꼭 방문 해제와 pop() 함수를 실행해야 한다.

 

5. sorted(lst) 부분을 통해, 같은 수 중복인 리스트를 제외시킨다.

 

6. 그냥 lst를 하면 모든 리스트가 동일하게 되므로, 

꼭 lst.copy()  또는 lst[:]의 방법으로 저장해줘야 한다. 

 

 

🗒️다른 파이썬 코드 풀이

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
visited = [0] * (N+1)
rs = []

def dfs(start):
    if len(rs) >= M:
        print(" ".join(map(str,rs)))
        return 
    
    for i in range(start,N+1):
        if i not in rs : 
            rs.append(i)
            dfs(i+1)
            rs.pop()
dfs(1)

 

1. 이 코드가 더 간결하다 .

 

2. 같은 수 반복을 피하기위해, 아래같은 방식을 dfs로 표현했다.

for i in range(1,N-1):
    for j in range(i+1,N):

 

3. 나머지 아래 부분은 전형적인 dfs 방식이다.

 

 

📌  문제 코멘트

같은 수 중복을 제거하는 로직에 대해 고민했었다.

 

처음에는 reverse 함수로 해보려했는데, 만일 M이 3 이상인 경우 문제가 생긴다.

그래서 정렬을 통해 중복을 제거하는 백트래킹을 해보았다. 

 

근데 다른 파이썬 풀이가 좀 더 괜찮은 풀이같다. 

 

---

📚문제

자연수 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 3
2 4
3 4

예제 입력 3 

4 4

예제 출력 3 

1 2 3 4