[python] 그래프 - (2)

문제 2. 전화 번호 문자 조합

2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.

• 입력 : "23" -> 출력 : ["ad", "ae", "af", "bd", "be", "bf" , "cd", "ce", "cf"]

풀이 - 모든 조합 탐색

def letterCombinations(digits):
    def dfs(index, path):
        # 끝까지 탐색하면 백트래킹
        if len(path) == len(digits):
            result.append(path)
            return
        
        # 입력값 자릿수 단위 반복
        for i in range(index, len(digits)):
            # 숫자에 해당하는 모든 문자열 반복
            for j in dic[digits[i]]:
                dfs(i+1 , path + j)
    
    # 예외 처리
    if not digits:
        return []
    
    dic = { "2": "abc", "3":"def","4":"ghi","5":"jkl",
          "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
    result = []
    dfs(0,"")
    
    return result

입력 : 23

실행결과

["ad", "ae", "af", "bd", "be", "bf" , "cd", "ce", "cf"]

• 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.
• 이 함수에서 digits는 입력값이며, 각 자릿수에 해당하는 키판 배열을 DFS로 탐색하면 결과가 완성된다.

문제 3. 순열

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.

• 입력 : [1,2,3]
• 출력 : [ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

풀이 1 . DFS를 활용한 순열 생성

def permute(nums):
    results = []
    prev_elements = []
    
    def dfs(elements):
        #리프 노드일 때 결과 추가
        if len(elements) == 0 :
            results.append(prev_elements[:])
        # 순열 생성 재귀 호출
        for e in elements:
            next_elements = elements[:]
            next_elements.remove(e)
            
            prev_elements.append(e)
            
            dfs(next_elements)
            prev_elements.pop()
            
    dfs(nums)
        
    return results

• elements 의 원소가 하나도 남지 않았을 떄의 prev_elements를 results 리스트에 추가시키는 조건을 DFS 함수의 제일 처음에 놓는다.
• 그 후 재귀를 활용해 모든 조합의 순열을 구해주면 된다.

풀이 2. itertools 모듈 사용

import itertools
def permute(nums):
    return list( map( list , itertools.permutations(nums)))

• itertools 모듈에는 순열을 구하는 함수가 내장되어 있기 때문에 호출해서 사용할 수 있다.

문제 4. 조합

전체 수 n을 입력받아 k개의 조합을 리턴하라.
ex)

• 입력 : n = 4 , k = 2
• 출력 : [ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ]

DFS로 k개 조합 생성

def combine(n,k):
    results = []
    
    def dfs(elements, start, k):
        if k == 0:
            results.append(elements[:])
            
        # 자신 이전의 모든 값을 고정하여 재귀 호출
        for i in range(start, n+1):
            elements.append(i)
            dfs(elements, i+1 , k-1)
            elements.pop()
    
    dfs([],1,k)
    return results

• 순열에서는 자기 자신을 제외하고 모든 요소를 next_elements로 처리했으나, 조합에서는 자기 자신뿐만 아니라 앞의 모든 요소를 배제하고 next_elements를 구성한다.

• 그 후 재귀를 활용해 DFS로 모든 조합을 구해주면 된다.

itertools 모듈 사용

def combine(n,k):
    return list(map(list, itertools.combinations(range(1,n+1), k )))

• 순열과 마찬가지로 조합 또한 itertools 모듈에 내장되어 있는 함수가 있다.

문제 5. 조합의 합

숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.

ex)

• 입력 : candidates = [2,3,6,7] , target = 7
• 출력 : [ [7] , [2,2,3] ]

DFS로 중복 조합 그래프 탐색

def combinationSum(candidates,target):
    result = []
    
    def dfs(csum, index, path):
        #종료 조건
        if csum < 0 :
            return
        if csum == 0:
            result.append(path)
            return
        
        # 자신 부터 하위 원소 까지의 나열 재귀 호출
        for i in range(index, len(candidates)):
            dfs(csum - candidates[i], i, path + [candidates[i]])
            
    dfs(target, 0 , [])
    return result

• target 숫자에 하나씩 원소를 빼면서 DFS를 통해 모든 조합의 수를 계산해보며 csum (target이 입력되고 원소를 하나씩 빼고있는 변수) 이 0보다 작아지거나 0이되면 종료조건을 발동시킨다.

• csum 이 0이 되는경우는 조건을 제대로 찾은 것이기 때문에 path를 result에 추가시킨다.

• 순열의 합으로 문제를 해결하고 싶다면 dfs 안에 재귀문 dfs에 두번째 입력값(index)를 i 대신 0 을 넣으면 된다.

• 이를 통해 중복 조합의 합으로 만들 수 있는 target 의 조합을 구할 수 있다.