[자료구조/코테] 그래프

그래프

 

 

 

 

최단경로

- 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제 

- (Wiki) 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제

 

 

알고리즘종류

(1) 다익스트라 : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제

(2) 벨먼-포트 알고리즘 : 변의 가중치가 음수라면 단일 출발 문제

(3) A* 탐색 알고리즘 : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있음 

(4) 플로이드-와셜 알고리즘 :  전체-쌍 최단 경로 문제를 풀 수 있음 

 

 

17. Letter Combinations of a Phone Number

 

 

 

39. Combination Sum

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:       
        
        
        def dfs(_nums,_tmp):
            if not _nums:
                result.append(_tmp);
                return; 
            
            for i in range(len(_nums)):
                dfs(_nums[:i] + _nums[i+1:], _tmp + [_nums[i]])
            
                
        result = []
        dfs(nums, []) 
        return result;

 

 

 

 

46. Permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:       
        
        
        def dfs(_nums,_tmp):
            if not _nums:
                result.append(_tmp);
                return; 
            
            for i in range(len(_nums)):
                dfs(_nums[:i] + _nums[i+1:], _tmp + [_nums[i]])
            
                
        result = []
        dfs(nums, []) 
        return result;

(1) result 바깥에 있 때문에 종료 return만 해줌, 추가하면서 하는건 return A; 

(2) dfs(_nums[:i] + _nums[i+1:], _tmp + [_nums[i]]), 현재 추가하는걸 제외하고 나머지를 다시 넣음 

 

 

77. Combinations

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

(1) 방법 -> DFS 사용 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        tmp = list(map(lambda x : x, range(1, n+1)))
        
        def dfs(_numberList, _route):
            if len(_route) == k :
                result.append(_route)
                return;
            
            for i in range(0, n):
                dfs(_numberList, _route + [_numberList[i]]);               
        
        result = []; 
        dfs(tmp, [])
        print(result) 
        # [[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], 
        # [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]]

 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        tmp = list(map(lambda x : x, range(1, n+1)))
        
        def dfs(_numberList, _route):
            if len(_route) == k :
                result.append(_route)
                return;
            
            for i in range(0, n):
                if len(_route) > 0 :
                    if _route[-1] < _numberList[i] : 
                        dfs(_numberList, _route + [_numberList[i]]);               
                else:
                    dfs(_numberList, _route + [_numberList[i]]);      
        result = []; 
        dfs(tmp, [])
        return result;

 

(2) itertools 사용

1. itertools.combinations() 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1,n+1), k))

 

 

78. Subsets

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        def dfs(_route):
            result.append(_route)
            
            for num in nums:
                if len(_route) > 0 :
                    if _route[-1] < num : 
                        dfs(_route + [num]);
                else:
                    dfs(_route + [num])
            
            
            
        
        result = []; 
        dfs([])
        return result;

200. Number of Islands

 

 

 

 

207. Course Schedule

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list);
        
        for x, y in prerequisites:
            graph[x].append(y)
            
        
        traced = set();
        
        print(graph)
        
        def dfs(i):
            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;

 

 

 

332. Reconstruct Itinerary

- DFS로 구성하거나 

- 파이썬 리스트의 경우 지정하지 않은 값, 마지막 값을 꺼내는 pop()은 O(1)이지만, 첫번째 값을 꺼내는 pop(0)은 O(n)이다. 

- 좀 더 효율적인 구성을 위해서는 스택연산으로 구현하는게 필요 

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        
        def dfs(_route):
            print(graph)
            while graph[_route[-1]]:
                _route.append(graph[_route[-1]].pop())
                return dfs(_route)
            
            return _route
        
        graph = collections.defaultdict(list);
        
        for a,b in sorted(tickets):
            graph[a].append(b)
        
        route = dfs(['JFK'])
        
        return route

 

 

 

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        
        graph = collections.defaultdict(list);
        
        for a,b in 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(0))
        
        return route

 

 

 

743. Network Delay Time

- 네트워크 딜레이 타임 

- 다익스트라 알고리즘? 임의의 정점을 출발 집합에 더할떄, 그 정점까지의 최단거리는 계산이 끝났다는 확인을 갖고 더함 

 

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        
        #그래프 인접 리스트 구성
        for u, v, w in times:
            graph[u].append((v,w));
            
        #큐변수 [(소요시간, 정점)]
        Q = [(0,k)]
        
        dist = collections.defaultdict(int);
        
        #우선순위 큐 최솟값 지누으로 정점까지 최단 경로 삽입 
        while Q:
            time, node = heapq.heappop(Q)
            
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    alt = time + w
                    heapq.heappush(Q, (alt,v));
                                   
        if len(dist) == n:
            return max(dist.values())
        return -1

 

 

 

 

 

787. Cheapest Flights Within K Stops

 

 

 

 

 

 

 

 

 

1631. Path With Minimum Effort