[python] 백준 15650번 : N과 M(2)

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

15650번: N과 M (2)

삼성 코딩테스트 같은 경우, itertools 모듈을 사용할 수 없습니다.

그래서 permutations(순열)이나 combinations(조합) 같은 기능을 사용하지 못하는데,

이를 대비하기 위해 DFS를 이용하여 조합을 구할 수 있는 대표적인 문제입니다.

 

[dfs]

def dfs(arr, idx):
    if len(arr) == M:
        print(*arr)
        return

    for i in range(idx, N):
        if not lst[i] in arr:
            arr.append(lst[i])
            dfs(arr, i+1)
            arr.pop()


N, M = map(int, input().split())
lst = [i for i in range(1, N+1)]
dfs([], 0)

 

[코드개선]

not in 구문이 아닌 visited 배열을 선언함으로써 해당 구간에서의 시간복잡도를 O(n)에서 O(1)로 줄일 수 있습니다.

def dfs(arr, idx):
    if len(arr) == M:
        print(*arr)
        return

    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            arr.append(lst[i])
            dfs(arr, i+1)
            visited[i] = False
            arr.pop()


N, M = map(int, input().split())
visited = [False for _ in range(N)]
lst = [i for i in range(1, N+1)]
dfs([], 0)

 

[코드 개선2] ☆☆☆☆

idx라는 매개변수가 for문에서 접근 가능한 인덱스에 제한을 두고 있기 때문에 visited 배열이나 not in 구문을 사용하지 않아도 됩니다. 

def dfs(arr, idx):
    if len(arr) == M:
        print(*arr)
        return

    for i in range(idx, N):
        arr.append(lst[i])
        dfs(arr, i+1)
        arr.pop()


N, M = map(int, input().split())
lst = [i for i in range(1, N+1)]
dfs([], 0)

 

for문이나 not in 구문을 사용하지 않아도 되는 이유는 아래 로직을 보면 알 수 있습니다.  

arr 배열에 현재 추가하는 변수의 인덱스 값을 dfs에 idx로 넣어 for문에서 자신보다 오른쪽에 있는 변수들만 접근함으로써 중복 카운팅(1 2 방문 후 2 1 방문 안함, 2 2 도 방문 안함)을 막을 수 있습니다. 

 

[로직 동작원리]

def dfs(arr, idx):
    if len(arr) == M:
        print('출력:', *arr)
        return

    for i in range(idx, N):
        arr.append(lst[i])
        print('arr =',arr,)
        print('dfs(',arr,',',i+1,')')
        dfs(arr, i+1)
        arr.pop()
        print()
    print('**************')
    print()


N, M = map(int, input().split())
lst = [i for i in range(1, N+1)]
dfs([], 0)