비선형 자료구조 - 그래프 ll
해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.
조합의 합
숫자 집합을 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
- 풀이: DFS로 중복 조합 그래프 탐색
class Solution:
def combinationSum(self, candidates: List[int], target: int) \
-> List[List[int]]:
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
부분 집합
모든 부분 집한을 리턴하라.
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
- 풀이: 트리의 모든 DFS 결과
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
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
일정 재구성
[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다.
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
- 풀이: DFS로 일정 그래프 구성
import collections
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# collections.defaultdict로 딕셔너리 구성
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]
- 풀이: 스택 연산으로 큐 연산 최적화 시도
앞선 풀이 방법 중 pop()은 O(1)이지만, pop(0)은 O(n)이 된다. 공간복잡도를 조금 더 최적화 하기 위해 스택의 연산으로 처리 될 수 있도록 수정하자.
import collections
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
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]
- 일정 그래프 반복
import collections
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
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]
코스 스케쥴
0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0, 1] 쌍으로 표현하는 n개의 코스가 있다. 코수 개수 n과 이 쌍들의 입력을 받았을 때 모든 코스가 완료 가능한지 판별하라.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
---
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
- 풀이: DFS로 순환 구조 판별
import collections
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()
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
- 풀이: 가지치기를 이용한 최적화
import collections
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()
visited = set()
def dfs(i):
# 순환 구조이면 False
if i in traced:
return False
# 이미 방문했던 노드이면 True
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
