https://leetcode.com/problems/combination-sum/
조합의 합
from typing import List
class Solution:
'''
DFS로 중복 조합 그래프로 탐색
'''
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
https://leetcode.com/problems/course-schedule/
코스 스케줄
import collections
from typing import List
class Solution:
'''
풀이 1: DFS로 순환 구조 판별
'''
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):
print(f'i:{i}')
# 순환 구조이면 False
if i in traced:
return False
traced.add(i)
print(f'traced:{traced}')
print(f'graph:{graph[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
https://www.acmicpc.net/problem/1260
DFS와 BFS
from collections import deque
num, line_num, start = map(int, input().split())
graph = [[0] * (line_num + 1) for _ in range(line_num + 1)]
for _ in range(line_num):
head, tail = map(int, input().split())
graph[head][tail] = graph[tail][head] = 1
def bfs(index):
bfs_visited = [index]
queue = deque()
queue.append(index)
while queue:
start = queue.popleft()
print(start, end=' ')
for sub in range(len(graph[start])):
if graph[start][sub] == 1 and (sub not in bfs_visited):
bfs_visited.append(sub)
queue.append(sub)
def dfs(index, dfs_visited = []):
dfs_visited.append(index)
print(index, end=' ')
for sub in range(len(graph[index])):
if graph[index][sub] == 1 and (sub not in dfs_visited):
dfs(sub, dfs_visited)
dfs(start)
print()
bfs(start)https://leetcode.com/problems/reconstruct-itinerary/
일정 재구성
'''
답안 1 DFS로 일정 그래프 구성
내 고민이 무색하게 코드는 너무 간단함
sort 전처리는 기본이니 넘어감
dfs 진입 시
사전순으로 목적지들을 꺼내옴
해당 목적지를 꺼낼 때 pop을 이용해 다시 그 경로를 이용하지 못하도록 함
즉, 방문한 리스트를 따로 만들거나, if로 검증할 필요가 없음
뽑은 목적지로 다시 dfs를 돌림
즉,
JFK -> KUL -> X
-> NRT -> JFK -> x
순번으로 진행 됨
목적지가 route에 추가되는 순간은
하위에 모든 요소가 루틴을 다 돌고 난 이후임
위에서 오른쪽 순으로 연산이 끝난다고 했을때(가장 깊은 순으로)
KUL은 하위에 아무런 요소가 없기 때문에 추가됨
그 다음으로 MRT -> NRT -> JFK에서
마지막 JFK는 더이상 하위요소가 없어서 연산이 끝나 KUL이후 -> JFK
JFK연산이 끝나고 상위에 NRT도 더이상 요소가 없기 때문에 종료 후 추가
KUL은 이전에 끝났으니 상위로 돌아가 JFK요소 또안 NRT이 끝난 순간 더이상 요소가 없음
KUL -> JFK -> NRT -> JFK
리스트 추가를 깊은 순으로 했으니 [::-1]로 역순으로 출력
찾아간 목적지 리스트가 완성 됨
'''
def findItineraryDFS(self, tickets: List[List[str]]) -> List[str]:
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]
'''
풀이 2: 스택 연산으로 큐 연산 최적화 시도
이전에는 큐 연산을 수행했음
다만 첫 번째 값을 꺼내는 pop(0)는 성능이 안좋음(deque는 제외)
따라서 효율적인 연산을 위해 pop()방식을 사용한 스택을 이용
별건없고 그냥 그래프 준비 할때 반대로 만듬
'''
def findItinerary(self, tickert: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
# 그래프를 뒤집어서 구성
for a, b in sorted(tickert, reverse=True):
graph[a].append(b)
route = []
def dfs(a):
# 마지막 값을 읽어 어휘 순 방문
while graph[a]:
dfs(graph[a].pop())
route.append(a)
dfs('JFX')
# 다시 뒤집어 어휘 순 결과로
return route[::1]
'''
풀이 3: 일정 그래프 반복
재귀가 아닌 동일한 구조를 반복으로 풀이
대부분의 재귀 문제는 반복으로 치환 가능하며 스택으로 풀이가 가능
그래프 구성은 동일하지만 끄집어 낼때 스택을 이용한 반복 처리
'''
def findItineraryRepeat(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]https://leetcode.com/problems/subsets/
부분 집합
from typing import List
'''
'''
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
그래프가 나오기 시작하고 내 알고리즘도 같이 조졌다
아....난 뭐하고 있는거지 싶다.
그냥 정답을 외우면 편하려나
달콤살벌