[python] 그래프 - (3)

JunHyeok Oh·2021년 7월 20일

파이썬알고리즘인터뷰_SelfStudy

목록 보기

15/16

문제 6. 부분 집합

모든 부분 집합을 리턴하라.

트리의 모든 DFS 결과

def subsets(nums):
    result = []
    
    def dfs(index, path):
        # 매번 결과 추가
        result.append(path)
        
        #경로를 만들면서 DFS
        for i in range(index, len(nums)):
            dfs(i+1 , path + [nums[i]])
            
    dfs(0,[])
    return result

경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태로 깊이 탐색하는 방법이다.
별도의 종료조건은 없다.
path의 결과를 매번 result 리스트에 추가시켜 모든 부분집합을 구할 수 있다.

문제 7. 일정 재구성

[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다.

ex )

입력 : [ [ "MUC" , "LHR" ] , ["JFK" , "MUC" ] , [ "SFO" , "SJC" ] , ["LHR" , "SFO" ] ]
출력 : ["JFK" , "MUC" , "LHR" , "SFO" , "SJC" ]

DFS로 일정 그래프 구성

import collections
def findItinerary(tickets):
    graph = collections.defaultdict(list)
    #그래프 순서대로 구성
    for a,b in sorted(tickets):
        graph[a].append(b)
        
    route = []
    def dfs(a):
        # 첫 번째 값을 읽어 어휘 순으로 방문
        while graph[a]:
            dfs(graph[a].pop(0))
        route.append(a)
    
    dfs('JFK')
    #다시 뒤집어 어휘 순 결과로
    return route[::-1]

이 문제에서 주의할 점은 여러 일정이 겹칠 때, 알파벳 오름차순을 기준으로 먼저 방문하는 점이다.
일단 출발지가 key이고 도착지가 value인 딕셔너리를 제작한다. defaultdict을 통해 실제 딕셔너리에 key가 없는 값을 append해도 list를 디폴트로 생성해준다.
첫번째 넣는 입력 값을 'JFK'로 하고 DFS를 작동시키면, 딕셔너리에서 key가 JFK인 값의 value를 출력하고 또 이어서 그 value가 key에 해당하는 값의 value를 DFS 하고 반복하면서 graph가 빈 딕셔너리가 될 때 까지 반복한다.
하지만 이때 route에 append 되는 순서는 가장 최근 방문지부터 추가되고 마지막으로 JFK가 추가되므로 route[::-1]로 뒤집어 주면 우리가 원하는 결과를 얻을 수 있다.

스택 연산으로 큐 연산 최적화 시도

import collections
def findItinerary(tickets):
    graph = collections.defaultdict(list)
    #그래프 순서대로 구성
    for a,b in sorted(tickets,reverse=True):
        graph[a].append(b)
        
    route = []
    def dfs(a):
        # 첫 번째 값을 읽어 어휘 순으로 방문
        while graph[a]:
            dfs(graph[a].pop())
        route.append(a)
    
    dfs('JFK')
    #다시 뒤집어 어휘 순 결과로
    return route[::-1]

pop(0) 함수는 pop() 에 비해 비효율적이므로, 처음 딕셔너리를 저장할때 사전어휘순의 내림차순으로 append를 하고 dfs함수에서 pop()를 통해 마지막 값부터 빼는 방식이다.
리스트가 크다면 효율성의 개선이 이루어 질 것이다.( pop(0) : O(1) , pop(): O(n) )

일정 그래프 반복

import collections
def findItinerary(tickets):
    graph = collections.defaultdict(list)
    #그래프 순서대로 구성
    for a,b in sorted(tickets):
        graph[a].append(b)
        
    route, stack = [] , ['JFK']
    
    while stack:
        # 반복으로 스택을 구성하되 막히는 부분에서 풀어내는 처리
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop(0))
        route.append(stack.pop())
    
    #다시 뒤집어 어휘 순 결과로
    return route[::-1]

DFS 대신 stack을 통해 반복하는 방식이다. 안에 있는 while문은 graph 딕셔너리의 stack의 마지막 값의 value 리스트가 비어있을 때까지 진행하게 된다.
stack에는 가장 최근 방문지가 append 되고 route에 저장되면서 빠지게 된다.
이 풀이도 마찬가지로 경로가 거꾸로 저장되어 있으므로 route[::-1]을 리턴한다.

문제 8. 코스 스케줄

0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.

ex)

입력 : 2 , [[1,0]]
출력 : true
2개의 코스가 있으며, 1을 완료하기 위해 0을 끝내면 된다. 따라서 가능하다.
입력 : 2 , [[1,0],[0,1]]
출력 : false
2개의 코스가 있으며, 1을 완료하기 위해 0을 끝내면 된다. 하지만 0을 끝내기 위해서는 1을 끝내야 한다. 따라서 불가능하다.

DFS로 순환 구조 판별

def canFinish(numCourses,prerequisites):
    graph = collections.defaultdict(list)
    
    #그래프 구성
    for x,y in prerequisites:
        graph[x].append(y)
    
    traced = set()
    
    def dfs(i):
        # 순환 구조이면 False
        if i in traced:
            return False
        
        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False
        #탐색 종료후 순환 노드 삭제
        traced.remove(i)
        
        return True
    
    # 순환 구조 판별
    for x in list(graph):
        if not dfs(x):
            return False
        
    return True

이 문제는 그래프가 순환구조인지를 판별하는 문제이다. ( 순환구조면 다시 제자리로 맴돌게 되므로 처리할 수 없다. )
이전 문제와 마찬가지로 defaultdict을 활용해 기본값이 존재하는 딕셔너리를 만들어 준다.
순환구조를 판별하기 위해 이미 방문했던 노드를 traced 변수에 저장한다. 이미 방문했던 곳을 중복 방문하게 된다면 순환 구조로 간주할 수 있고, 이 경우 False를 리턴하고 종료하면 된다.
traced 는 중복값을 가지지 않으므로 set() 자료형을 활용한다. 그리고 탐색 종료 후 순환 노드를 꼭 삭제해야한다. 만약 하지 않으면 자식 노드 입장에서 순환이라고 잘못 판단할 여지가 생기기 때문이다.
결국 DFS 함수인 dfs() 에서 현재 노드가 이미 방문했던 노드 집합인 traced에 존재한다면 순환 구조 이므로 False를 리턴하는 방법이다.

가지치기를 이용한 최적화

def canFinish(numCourses,prerequisites):
    graph= collections.defaultdict(list)
    # 그래프 구성
    for x,y in prerequisites:
        graph[x].append(y)
    
    traced = set()
    visited = set()
    
    def dfs(i):
        # 순환 구조이면 False
        if i in traced:
            return False
        # 이미 방문했던 노드이면 False
        if i in visited:
            return True
        
        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False
            
        #탐색 종료 후 순환 노드 삭제
        traced.remove(i)
        # 탐색 종료 후 방문 노드 추가
        visited.add(i)
        
        return True
    
    #순환 구조 판별
    for x in list(graph):
        if not dfs(x):
            return False
        
    return True