[백준알고리즘] 15649번: N과 M (1) -Python

[백준알고리즘] 15649번: N과 M (1) -Python

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

15649번: N과 M (1)

 

오랜만에 백준에 들어가니 BackTracking이 있었다. 예전에도 있었나 모르겠지만 처음 본 것 같아서 풀어봤다. 근데 1번째 문제라 그런지 백트랙킹 문제라기보다는 DFS 같았다.

그래서 그냥 DFS로 풀었다. :)

 

두 가지 방법으로 풀었는데 첫 번째는 DFS로 풀었고 두 번째 풀이는 itertools 모듈을 이용해서 풀었다.

 

itertools는 for문을 사용하지 않고도 permutations를 이용하면 순열을 쉽게 얻을 수 있다. 게다가 문제에서 원하는 데로 오름차순으로 순열을 얻을 수 있다.

 

itertools를 이용한 방법이 코드도 짧고 속도 차이도 많이 났다. 여기서 join을 이용해주기 위해서 리스트 값들을 모두 str으로 변환해주었다. 이 점을 제외하고는 itertools가 훨씬 사용하기 편하다. 

위의 결과가 itertools 아래 결과가 DFS

 

첫 번째 DFS로 푼 풀이이다.

import sys

def testCase():
    input_val = list(map(int, sys.stdin.readline().split()))
    global N, M
    N, M = input_val

def dfs(remain, result = []):
    if len(result) == M:
        # print
        for i in result:
            print(i, end=" ")
        print()
        return
        
    # dfs
    for r in remain:
        remain.remove(r)
        result.append(r)

        dfs(remain, result)

        remain.append(r)
        remain.sort()
        result.pop(-1)


if __name__ == "__main__":
    testCase()
    dfs(list(range(1, N+1)))

 

두 번째 itertools를 이용한 풀이이다.

import sys
import itertools

def testCase():
    input_val = list(map(int, sys.stdin.readline().split()))
    global N, M
    N, M = input_val

def solve(remain):
    res = list(map(' '.join, itertools.permutations(remain, M)))
    print('\n'.join(res))

if __name__ == "__main__":
    testCase()
    solve(map(str, list(range(1, N+1))))

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다