📌 32) 섬의 개수 (리트코드 200. Number of Islands )
✔ 풀이 (DFS_recursion)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
#중첩함수
def dfs(i, j):
#값이 '1'이 아니거나 범위를 벗어나면 종료
if (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid[0])) or grid[i][j] != '1':
return
grid[i][j] = '0' #다시 방문하지 않도록 값 변경
#동서남북으로 재귀 호출
dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)
cnt = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
cnt += 1
return cnt📝 재귀함수 종료조건에서 grid[i][j] != '1'가 (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid[0])) 보다 앞에 있으면 IndexError: list out of range(Runtime Error) 발생
📌 33) 전화 번호 문자 조합 ( 리트코드 17. Letter Combinations of a Phone Number )
✔ 풀이 (DFS_recursion = 백트래킹)
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
#중첩함수
def dfs(index, path):
#재귀 종료 조건 -> 끝까지 탐색하면 백트래킹
if len(path) == len(digits):
answer.append(path)
return
for char in num_dic[digits[index]]:
dfs(index + 1, path + char)
#예외처리-> input이 digits = ""일 경우
if not digits: #빈 문자열이면 if, while같은 문의 조건에서 거짓으로 간주
return []
num_dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
answer = []
dfs(0, "")
return answer📌 34) 순열 ( 리트코드 46. Permutations )
✔ 풀이 (DFS_recursion)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
answer, prev_e = [], []
def dfs(elements):
#재귀함수 종료조건
if not elements:
answer.append(prev_e[:])
return
for e in elements:
#elements을 prev_e와 next_e로 나눔
next_e = elements[:] #파이썬은 객체를 참조함에 유의
next_e.remove(e) #현재값을 제외한 요소들을 next_e에
prev_e.append(e) #현재값을 prev_e에 위치하게 함
dfs(next_e)
prev_e.pop() #재귀함수 종료휴 prev_e = []로 만들기 위해 하나 씩 pop
dfs(nums)
return answer📝 next_e = elements 안하고 next_e = elements[:] 한 이유는 파이썬은 모든 객체를 참조하는 형태로 처리되기 때문임
=>next_e = elements 하면 elements가 변경될때마다 next_e의 값이 변경됨.
next_e = elements[:]하면 elements.copy()와 같이 값은 같지만 다른 객체를 가리킴
✔ 풀이 (itertools.permutations 모듈 사용)
from itertools import permutations
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(map(list, permutations(nums)))📌 35) 조합 ( 리트코드 77. Combinations )
✔ 풀이_1 (DFS_recursion)
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
answer, prev_e = [], []
def dfs(elements, cnt):
#재귀함수 종료조건
if not cnt:
answer.append(prev_e[:])
return
for idx, e in enumerate(elements):
next_e = elements[idx + 1:]
prev_e.append(e)
dfs(next_e, cnt - 1)
prev_e.pop()
dfs([num for num in range(1, n + 1)], k)
return answer✔ 풀이_2 (DFS_recursion)
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
answer = []
def dfs(elements, start, cnt):
#재귀함수 종료조건
if not cnt:
answer.append(elements[:])
return
for i in range(start, n + 1):
elements.append(i)
dfs(elements, i + 1, cnt - 1)
elements.pop()
dfs([], 1, k)
return answer✔ 풀이 (itertools.combinations 모듈 사용)
from itertools import combinations
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
return list(map(list, combinations([num for num in range(1, n+1)], k)))📌 36) 조합의 합 ( 리트코드 39. Combinations Sum )
✔ 풀이(DFS_recursion)
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
answer = []
#재귀 함수
def dfs(c_sum, idx, path):
#재귀함수 종료조건 => target값 초과했을 경우
if c_sum < 0:
return
#재귀함수 종료조건 => target값 일 경우
if c_sum == 0:
answer.append(path)
return
for i in range(idx, len(candidates)):
dfs(c_sum - candidates[i], i, path + [candidates[i]])
dfs(target, 0, [])
return answer📝 입력값중 0이 포함되어 있으면? => 종료조건을 만족할 수 없기 때문에 무한히 깊이 탐색을 시도
📌 37) 부분 집합 ( 리트코드 78. Subsets )
✔ 풀이(DFS_recursion)
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
answer = []
def dfs(idx, path):
answer.append(path) #매번 추가
for i in range(idx, len(nums)):
dfs(i + 1, path + [nums[i]])
dfs(0, [])
return answer📌 38) 일정 재구성 ( 리트코드 332. Reconstruct Itinerary )
✔ 풀이 (DFS_recursion = 백트래킹)
from collections import defaultdict
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
#그래프 구성
#pop()하면 사전어휘순으로 나올 수 있도록 내림차순 정렬
graph = defaultdict(list)
for start, end in sorted(tickets, reverse = True):
graph[start].append(end)
#재귀dfs (백트래킹 하여 경로 역순으로 추가)
route = []
def dfs(start):
while graph[start]:
dfs(graph[start].pop())
route.append(start)
dfs('JFK')
#경로를 역순으로 추가했으므로 다시 역순으로 바꾸어 return
return route[::-1]✔ 풀이 (일정 그래프 반복)
from collections import defaultdict
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
#그래프 구성
graph = defaultdict(list)
for start, end in sorted(tickets, reverse = True):
graph[start].append(end)
#dfs
stack, route = ['JFK'], []
while stack:
while graph[stack[-1]]:
#어휘순서가 빠른 자식노드 stack추가 => 더 이상 자식노드가 없을때까지 탐색
stack.append(graph[stack[-1]].pop())
route.append(stack.pop()) #빠져나오면서 경로 추가
return route[::-1]📌 39) 코스 스케줄 ( 리트코드 207. Course Schedule )
그래프가 Cyclic(순환구조)인지 판별하는 문제
✔ 풀이_1 (DFS로 순환 구조 판별 => 시간제한 초과)
from collections import defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for after, before in prerequisites:
graph[after].append(before)
#dfs
traced = [] #이전에 방문했던 노드
def dfs(node):
if node in traced: #이전에 방문한 노드일경우
return False
traced.append(node)
for v in graph[node]:
if not dfs(v): #자식노드가 이전에 방문한 노드일경우
return False
#탐색 종료 후 순환 노드 삭제
traced.pop()
return True
#각 노드에서 출발하는 모든경우를 따지는 이유
#-> 그래프가 끊어져 있는 경우에서 cyclic 판별하기 위해!
for node in list(graph): #dict를 list로 변경하면 key만 list의 요소로 들어감
if not dfs(node): #dfs에서 False return될 경우
return False
return True✔ 풀이_2 (가지치기를 이용한 최적화)
from collections import defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for after, before in prerequisites:
graph[after].append(before)
#dfs
visited, traced = [], [] #순환구조 판별 완료한 노드, 이전에 방문했던 노드
def dfs(node):
if node in traced: #이전에 방문한 노드일경우
return False
if node in visited:
return True
traced.append(node)
for v in graph[node]:
if not dfs(v): #자식노드가 이전에 방문한 노드일경우
return False
traced.pop() #탐색 종료 후 순환 노드 삭제
visited.append(node) #순환구조 판별 완료
return True
#각 노드에서 출발하는 모든경우를 따지는 이유
#-> 그래프가 끊어져 있는 경우에서 cyclic 판별하기 위해!
for node in list(graph): #dict를 list로 변경하면 key만 list의 요소로 들어감
if not dfs(node): #dfs에서 False return될 경우
return False
return True📝 풀이1은 순환이 발견될 때까지 모든 자식 노드를 탐색하는 구조 -> 불필요하게 동일한 그래프를 여러번 탐색
풀이2는 한번 방문했던 그래프는 두 번 이상 방문하지 않도록 무조건 True로 return하는 구조로 개선 -> 가지치기로 최적화한 풀이
📝 for node in list(graph)에서 dict를 list로 형변환하는 이유?
하지 않으면 RuntimeError: dictionary changed size buring iteration 발생
-> graph = defaultdict(list)로 선언하여 빈 값 조회시 오류를 내지 않기 위해 항상 디폴트를 생성하는 구조로 되어 있으므로 graph값이 변경된다는 오류가 발생
-> list()로 묶을 경우 새로운 복사본이 생성되면서 다른 ID를 갖게 됨
