[백준/파이썬] 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

 

---

사고 흐름

1. N까지의 자연수 중에서 M 길이 만큼의 수열 구하기 

2. dfs를 사용해 방문한 node(자연수)를 만들어 길이가 M이 되면 return한다

 

문제 핵심과 알고리즘

모든 자연수를 M 만큼 탐색해야 하므로 dfs를 사용해 길이가 M인 방문 리스트 구하는 문제

n, m = map(int, input().split())
nlist=[i+1 for i in range(n)]

def dfs(node, nlist, v) :

    if len(v)==m :
        print(' '.join(map(str, v)))
        return

    for i in range(len(nlist)) :
        if nlist[i] not in v :
            v.append(nlist[i])
            dfs(nlist[i], nlist, v)
            v.pop()

dfs(1, nlist, [])

문제 풀면서 헤맸던 부분

1. join

방문한 리스트 v를 출력하려는데 처음에는 ' '.join(v) 이렇게 했다. 그런데 오류가 나서 구글링을 해보니, join은 문자열을 반환해주는데 v는 숫자형 리스트라서 int를 map으로 str로 만들고 join 해야한다. 이런 간단한 수식은 암기하자!

 => 숫자형 리스트에 join 사용: ' '.join(map(str, intlist))

 

다른 사람 풀이 참고하여 배운 점

비슷하게 풀이했다