그래프
Question 32: 섬의 개수
1(육지), 0(물) 로 만들어진 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라.
입력:
11110
11010
11000
00000
출력:
1
내 풀이
그래프 순회에 대한 걔념이 확실하게 잡혀있지 않은 상태에서 일단 풀이를 보류하였다.
풀이 1: DFS로 그래프 탐색 (재풀이)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
# 더 이상 땅이 아닌 경우 종료
if i < 0 or i >= len(grid) or \
j < 0 or j >= len(grid[0]) or \
grid[i][j] != '1':
return
# 아무 문자로 설정해도 가능
grid[i][j] = '#'
# 동서남북 탐색
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
# 모든 육지 탐색 후 카운트 1 증가
count += 1
return count
중요 내용
- 입력리스트를 돌아가면서 검색하여 1(육지)인 경우 그 육지와 이어진 나머지 육지를 찾는다.
- 탐색한 육지가 섬일 경우 count를 1 증가시킨다.
- 이미 탐색한 육지일 경우 # (아무 문자나 가능하다)로 변경한다.
Question 33: 전화번호 문자조합 (재풀이)
2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라
입력: “23”
출력: [‘ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]
내 풀이
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def addLetter(word1:str, word2:str):
while len(stack) > 0:
for i in word1:
for j in word2:
combined_word.append(i+j)
if len(stack) > 0:
addLetter(combined_word, stack.pop())
return combined_word
num_letter_dict = {2:'abc', 3:'def',
4:'ghi', 5:'jkl',
6:'mno', 7:'pqrs',
8:'tuv', 9:'wxyz'}
if len(digits) == 0:
return
combined_word = []
stack = []
for digit in digits:
stack.append(num_letter_dict[int(digit)])
ans = addLetter(stack[-1],'')
return ans
- 재귀 함수를 통해 문제에 접근하였으나 실패하였다.
풀이 1: 모든 조합 탐색
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def dfs(index, path):
# 끝까지 탐색하면 백트래킹
if len(path) == len(digits):
result.append(path)
return
# 입력값 자릿수 단위 반복
for i in dic[digits[index]]:
dfs(index+1, path+i)
# 예외 처리
if not digits:
return []
dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
result = []
dfs(0, "")
return result
중요 내용
- 재귀함수의 작동원리를 정확히 이해하는 것이 중요하다.
- 재귀함수에는 인덱스 값과 이어붙일 문자열을 인수로 넣는다.
- 인덱스의 변화를 생각해가며 문제에 접근하도록 하자!
Question 34: 순열 (재풀이)
서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.
입력: [1,2,3]
출력: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
내 풀이
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(permutations: List[int]):
if len(permutations) == len(nums):
results.append(permutations)
else:
for i in nums:
if i not in permutations:
next_p = permutations[:]
next_p.append(i)
dfs(next_p)
lst: List[int] = []
results = []
dfs(lst)
return results
- 문제 33번과 비슷한 dfs 방법으로 문제를 풀었다.
결과
Runtime: 67 ms, faster than 27.66% of Python3 online submissions for Permutations. Memory Usage: 14 MB, less than 95.52% of Python3 online submissions for Permutations.
풀이 1: DFS를 활용한 순열 생성
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
results = []
prev_elements = []
def dfs(elements):
# 리프 노드일때 결과 추가
if len(elements) == 0:
results.append(prev_elements[:])
# 순열 생성 재귀 호출
for e in elements:
next_elements = elements[:]
next_elements.remove(e)
prev_elements.append(e)
dfs(next_elements)
prev_elements.pop()
dfs(nums)
return results
중요 내용
- dfs 함수에 넣는 인수는 반드시 dfs의 인수와 이름이 동일해서는 안된다.
- results.append(prev_elements[:]) 에서 prev_elements 를 그대로 넣으면 prev_elements에 대한 참조가 추가되어 참조될 값이 변경될 경우 같이 바뀌게 된다.
풀이 2: itertools 모듈 사용
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(map(list, itertools.permutations(nums)))
중요 내용
- itertools의 permutations 모듈을 사용하면 금방 풀이가 가능하다.
Question 35: 조합
전체 수 n을 입력받아 k개의 조합을 리턴하라
입력: n = 4, k = 2
출력: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
내 풀이
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def dfs(combs):
if len(combs) == k:
results.append(combs[:])
else:
if len(combs) == 0:
last_val = 1
else:
last_val = combs[-1]
for i in range(last_val,n+1):
if i not in combs:
next_combs = combs[:]
next_combs.append(i)
dfs(next_combs)
results = []
dfs([])
return results
- 순열을 생성하는 알고리즘과 거의 비슷한 코드로 작성하였다.
- 순열 알고리즘과 다른 점이라면 조합 배열의 마지막 요소를 별도로 지정하여서 그 요소가 반복문에서 최소값이 되도록 설정하였다.
결과
Runtime: 804 ms, faster than 14.34% of Python3 online submissions for Combinations. Memory Usage: 15.9 MB, less than 42.85% of Python3 online submissions for Combinations.
풀이 1: DFS로 k개 조합 생성
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
results = []
def dfs(elements, start: int, k: int):
if k == 0:
results.append(elements[:])
return
# 자신 이전의 모든 값을 고정하여 재귀 호출
for i in range(start, n + 1):
elements.append(i)
dfs(elements, i + 1, k - 1)
elements.pop()
dfs([], 1, k)
return results
중요 내용
- 내 풀이 방법과 비슷하나 여기서는 반복문의 시작하는 값을 dfs 인수로 설정할 수 있게 하였다.
- 재귀 구조를 돌고 나서 조합 요소의 마지막 값을 삭제함으로써 그 전에 값을 복사하는 과정을 생략하였다. 이렇게 하는 것과 값을 복사했을때의 실행 시간은 비슷하여 어느 방법을 사용해도 무방할 것 같다.
풀이 2: 파이썬다운 방식
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
return list(itertools.combinations(range(1, n+1), k))
중요 내용
- 순열 문제와는 달리 조합 문제의 경우 DFS와 모듈 사이의 성능 차이가 꽤 큰 편이다.
Question 36: 조합의 합 (재풀이)
숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.
입력: candidates = [2,3,6,7], target = 7
출력: [[2,2,3],[7]]
풀이 1: DFS로 중복 조합 그래프 탐색
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
results = []
def dfs(csum, index, path):
if csum < 0:
return
if csum == 0:
results.append(path)
return
for i in range(index, len(candidates)):
dfs(csum - candidates[i], i, path + [candidates[i]])
dfs(target, 0, [])
return results
중요 내용
- 중복 조합 그래프는 for문의 iterator 값을 재귀 함수의 다음 for문의 starting index 값으로 지정하는 방법으로 탐색이 이루어진다.
Question 37: 부분 집합 (재풀이)
모든 부분 집합을 리턴하라
입력: nums = [1,2,3]
출력: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
내 풀이
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
results = []
def dfs(elements, start):
results.append(elements[:])
if len(elements) == len(nums):
return
for i in range(start, len(nums)):
dfs(elements + [nums[i]], i+1)
dfs([], 0)
return results
- DFS 방법으로 풀었다.
- 조합 문제를 풀 때와 마찬가지로 for문의 iterator 값을 재귀 함수의 다음 for문의 starting index 값으로 지정하였다.
결과
Runtime: 80 ms, faster than 5.59% of Python3 online submissions for Subsets. Memory Usage: 14.2 MB, less than 33.49% of Python3 online submissions for Subsets.
풀이 1: 트리의 모든 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
중요 내용
- range에서 지정한 시작 값이 끝 값보다 큰 경우 해당 반복문을 실행하지 않는다.
- 여기서 result.append()에 path[:]가 아닌 그냥 path를 넣어도 실행되는 이유를 잘 모르겠다. path+[nums[i]]를 하며 path에 새로운 값에 대한 참조가 아닌 새로운 값이 생성되어 그런 것이라는 추측만 할 수 있었다.
Question 38: 일정 재구성
[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전식 순서로 방문한다.
입력: [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
출력: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
내 풀이
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
def dfs(results, next_ticket):
if len(results)-1 == len(tickets):
candidates.append(results[:])
else:
last_ticket = results[-1]
for idx in range(len(next_ticket)):
if last_ticket == next_ticket[idx][0]:
results.append(next_ticket[idx][1])
tickets_copy_copy = next_ticket[:]
del tickets_copy_copy[idx]
dfs(results, tickets_copy_copy)
results.pop()
def sort_func(x):
start_letter = ''
for i in x:
start_letter += i[0]
return start_letter
candidates = []
for ticket in tickets:
if ticket[0] == 'JFK':
init_result = ticket
tickets_copy = tickets[:]
tickets_copy.remove(ticket)
dfs(init_result, tickets_copy)
candidates.sort(key = sort_func)
return candidates[0]
- DFS 방법으로 풀었다.
- ticket으로 가능한 여행 경로를 모두 후보 리스트에 넣고 후보 리스트를 사전식 순서로 정렬하였다.
결과
특정 값을 넣을때 올바른 답을 출력하지 않는 오류가 발생하였다.
풀이 1: DFS로 일정 그래프 구성
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 = []
def dfs(a):
# 첫 번째 값을 읽어 어휘순 방문
while graph[a]:
dfs(graph[a].pop(0))
route.append(a)
dfs('JFK')
# 다시 뒤집어 어휘순 결과로
return route[::-1]
중요 내용
- 내가 풀이한 방법과는 매우 다르게 defaultdict 함수를 사용하여 간단하게 풀이하였다.
- sorted를 nested list에 사용하면 nested list 안의 요소를 기준으로 정렬한다.
풀이 2: 스택 연산으로 큐 연산 최적화 시도
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]
중요 내용
- pop() 함수는 시간 복잡도가 O(1) 인 반면 pop(0)은 시간 복잡도가 O(n) 이다. 따라서 스택 방법으로 푸는 것이 훨씬 더 효과적이다.
- 티켓을 정렬할 때 reverse=True 로 설정하여서 내림차순으로 정렬되게 하였다.
풀이 3: 일정 그래프 반복
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]
중요 내용
- 스택을 이용한 반복으로 처리를 하였다.
- route는 더 이상 진행할 경로가 없을 때를 위해서 만든 리스트이다.
Question 39: 코스 스케줄
0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.
입력: numCourses = 2, prerequisites = [[1,0],[0,1]]
출력: False
- 순환 구조가 되면 false를 리턴한다.
내 풀이
- 순환 구조를 판별하는 부분에서 계속 에러가 떠서 결국 풀지 못하였다.
풀이 1: DFS로 일정 그래프 구성
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]:
# 최종 결과를 False로 리턴하게 함
if not dfs(y):
return False
# 탐색 종료 후 순환 노드 삭제
traced.remove(i)
return True
# 노드를 하나씩 반복하며 순환 구조 판별
for x in list(graph):
# 최종 결과를 False로 리턴하게 함
if not dfs(x):
return False
return True
중요 내용
- defaultdict() 함수로 시작점과 종점의 위치를 나타내는 딕셔너리를 만든다.
- 노드를 하나씩 순환하며 순환 구조인지 판별한다.
- 판별이 끝나면 반드시 판별 여부를 검사하는 세트 변수를 초기화 시켜준다.
- 이렇게 실행했을때 불필요하게 동일한 그래프를 여러번 탐색하게 되므로 타임 에러가 뜬다.
- graph는 defaultdict이므로 반복문을 돌때마다 에러가 나지 않기 위해 값을 계속 추가해 나간다. 따라서 이러한 에러가 나지 않도록 리스트 형태로 만들어줘야 한다.
풀이 2: 가지치기를 이용한 최적화
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
중요 내용
- visited 변수에 이미 방문했던 노드면 스킵할 수 있도록 한 번 방문했던 노드를 저장한다.
- 이렇게 가지치기를 하면 실행시간이 훨씬 더 단축되어 타임에러가 뜨지 않는다.
Comments