※ 읽기에 앞서
본 시리즈는 개발자를 희망하지만 코딩테스트에 고통받는
대한민국의 모든 개발자 지망생들을 위해 작성되었습니다.코딩테스트는 전략적으로 접근해야합니다.
개발자를 희망하는 많은 이들이 처음 코딩테스트를 준비할 때,
막연히 문제 풀이를 많이 시도하거나, 단순히 문제집을 참고하는 경우가 많습니다.
최대한 많은 문제를 풀거나, 문제집을 참고하는 것이 틀린 방법은 아니지만 매우 비효율적입니다.
같은 유형의 문제를 풀어도 항상 새롭게 보이고, 시간도 얼마나 걸릴지 장담할 수 없습니다.
문제 유형을 체계적으로 분류하고, 각 유형에 맞는 풀이 방법을 익히는 것이
최소한의 노력으로 최대한의 결과를 얻을 수 있는 가장 효율적인 방법입니다.해당 시리즈의 목표와 전략은 다음과 같습니다.
코딩테스트를 통과하기 위한 전략에 초점을 맞추고 있습니다.
1. 코딩테스트를 만점받기 위한 시리즈가 아닙니다.
2. 모든 유형의 문제를 완벽하게 정복하려 하지 않습니다.
3. 시험에 자주 나오는 유형의 문제만을 완벽히 정복합니다.
4. 코딩테스트를 통과할 수 있을 정도의 점수만을 목표로 합니다.
5. 실제 시험에서 풀 수 있는 문제와 없는 문제를 명확히 구분합니다.
셀 수 없이 많은 모든 유형의 문제를 완벽하게 정복할 수 없을 뿐더러,
프로젝트에서 하드코딩으로 알고리즘을 구현하여 사용하는 경우도 드물고,
애초에 누군가 이러한 알고리즘을 적용하여 만든 라이브러리가 많기 때문입니다.📌 DFS 깊이우선탐색
시험에 자주 등장하는 DFS(Depth First Search) 문제 유형은
경로 찾기,연결 요소,플러드 필,
백트래킹,그래프 순회,사이클 찾기
6종류로 구분됩니다.
연결 요소 문제: 현재 노드를 기준으로 연결된 모든 노드를 탐색하는 문제플러드 필 문제: 그래프의 영역을 특정 색상으로 채우는 문제, 일명 땅따먹기 문제백트래킹 문제: 해를 찾는 도중 막히면, 되돌아가서 다시 해를 찾아가는 기법그래프 순회 문제: 임의의 한 노드에서 시작하여 모든 노드들을 한 번씩 방문하는 작업사이클 찾기 문제: 시작점과 방문점이 같은 경우가 존재하는지 찾는 문제
이 외에도 `위상 정렬` 등의 유형도 있으나, 시험에 잘 등장하지 않는 유형이고,
'경로 찾기' 유형의 경우 `Floyd-Warshall Algorithm`이 더 효율적입니다.만약 실제 시험에서 이와 같은 유형이 출제된다면, 과감하게 포기하고
전략적으로 풀 수 있는 다른 문제를 찾아 집중하는 것이
코딩테스트를 통과할 확률이 더 높습니다.`경로 찾기`, `연결 요소`, `플러드 필` 의 경우
BFS(Breadth First Search) 유형에도 존재하는 문제로
BFS와 DFS 중 편한 것을 골라 사용하면 됩니다.📌 DFS 기본형태
가장 기본적인 형태의
DFS공식입니다.
Graph는Dictionary,2D Array2가지로 제공됩니다.
📖 Graph Dictionary
Graph가Dictionary일 때,DFS기본공식입니다.
def dfs(curr_node, graph, visited):
visited.add(curr_node)
for next_node in graph[curr_node]:
if next_node not in visited:
dfs(next_node, graph, visited)
return visiteddef solution():
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
dfs('A', graph, visited)
return visited📖 Graph 2D Array
Graph가2D Array일 때,DFS기본공식입니다.
def dfs(row, col, graph, visited):
if 0 <= row < len(graph) and 0 <= col < len(graph[0]):
if graph[row][col] != 0 and (row, col) not in visited:
visited[row][col] = True
dfs(row - 1, col, graph, visited)
dfs(row + 1, col, graph, visited)
dfs(row, col - 1, graph, visited)
dfs(row, col + 1, graph, visited)def solution():
graph = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
]
visited = set()
for row in range(len(graph)):
for col in range(len(graph[0])):
dfs(row, col, graph, visited)
return visited📌 DFS 응용형태
다양한 응용 형태의
DFS공식입니다.
기본형태에 특정조건을 추가하는 것이 중요한 유형입니다.
📘 응용① 연결요소
📖 Graph Dictionary
특정노드를 기준으로 연결된 모든 요소를 찾는 DFS 공식입니다.
응용 포인트1: 모든 연결요소를 찾기 위해 모든 노드에 대해 DFS를 수행합니다.
응용 포인트2:visited방문여부를component를 사용해update()로 일괄 처리합니다.
# 여기서 visited는 사실 solution()의 component
def dfs(curr_node, graph, visited):
visited.add(curr_node)
for next_node in graph[curr_node]:
if next_node not in visited:
dfs(next_node, graph, visited)def solution(graph):
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['D']
}
visited = set()
connected_components = []
# 응용 포인트1: 각 노드에 대해 dfs 수행
for node in graph:
if node not in visited:
component = set()
dfs(node, graph, component)
# 응용 포인트2: visited 방문여부를 component로 처리
connected_components.append(component)
visited.update(component)
return connected_components📖 Graph 2D Array
특정노드를 기준으로 연결된 모든 요소를 찾는 DFS 공식입니다.
응용 포인트1: 각각의Row를Node로 가정하여 위와 동일하게 문제를 해결합니다.
응용 포인트2:visited방문여부를component를 사용해update()로 일괄 처리합니다.
응용 포인트3:2D Array형태의Graph에 따라 이동 조건이 추가됩니다.
def dfs(curr_node, graph, visited):
visited.add(curr_node)
for next_node in range(len(graph)):
if next_node not in visited:
# 응용 포인트3: 노드 연결 여부, 이동 가능 조건 확인
if graph[curr_node][next_node] == 1:
dfs(next_node, graph, visited)def solution():
graph = [
[0, 1, 0, 1, 0], # node 0 is connected to nodes 1 and 3
[0, 0, 1, 1, 0], # node 1 is connected to nodes 2 and 3
[0, 0, 0, 0, 1], # node 2 is connected to node 4
[0, 0, 0, 0, 1], # node 3 is connected to node 4
[0, 0, 0, 0, 0], # node 4 has no outgoing edges
]
visited = set()
connected_components = []
# 응용 포인트1: 각각의 Row를 Node로 생각
for node in range(len(graph)):
if node not in visited:
component = set()
dfs(node, graph, component)
# 응용 포인트2: visited 방문여부를 component로 처리
connected_components.append(component)
visited.update(component)
return connected_components📘 응용② 플러드 필
위와 같은 일종의 땅따먹기 형태의 문제에서 사용되는 DFS 공식입니다.
일반적으로 이러한 유형의 문제에서는 BFS보다 DFS가 더 효율적으로 알려져있습니다.
📖 Graph Dictionary
연결요소들의 집합을 다른 색으로 구분하는 DFS 공식입니다.
이러한 땅따먹기 유형의 문제는 보통 그래프를 2D Array로 제공합니다.
연결요소의 연장선상의 문제로, solution()에서 모두 순회하며 다른 집합도 찾습니다.
응용 포인트1:
응용 포인트2:
📖 Graph 2D Array
연결요소들의 집합을 다른 색으로 구분하는 DFS 공식입니다.
이러한 땅따먹기 유형의 문제는 보통 그래프를 2D Array로 제공합니다.
연결요소의 연장선상의 문제로, solution()에서 모두 순회하며 다른 집합도 찾습니다.
응용 포인트1: 모든 연결요소 집합을 탐색합니다.
응용 포인트2: 이동 조건을old_color로 확인합니다.
def dfs(row, col, graph, old_color, new_color):
# 응용 포인트2: 이동조건을 old_color로 검사
if 0 <= row < len(graph) and 0 <= col < len(graph[0]):
if graph[row][col] == old_color:
graph[row][col] = new_color
dfs(row - 1, col, graph, old_color, new_color)
dfs(row + 1, col, graph, old_color, new_color)
dfs(row, col - 1, graph, old_color, new_color)
dfs(row, col + 1, graph, old_color, new_color)def solution(sr, sc, graph):
new_color = 0
visited = set()
# 응용 포인트1: 모든 영역 탐색
for row in range(len(graph)):
for col in range(len(graph[0])):
if (row, col) not in visited:
visited.add((row, col))
new_color = new_color + 1
old_color = graph[row][col]
dfs(row, col, graph, old_color, new_color)
return graph📘 응용③ 백트래킹
추후 백트래킹 글을 따로 만들어 정리 필요
기본형태
def backtrack(result, target, graph):
if sum(result) == target:
return result
if sum(result) > target:
return
for i in range(len(graph)):
result.append(graph[i])
backtrack(result, target, graph[i:])
result.pop()def solution():
target = 7
graph = [2, 3, 6, 7]
answer = []
backtrack(answer, target, graph)📖 Graph Dictionary
📖 Graph 2D Array
2D BackTracking 문제라고 나왔는데, 연결요소 문제라고함, 확인 필요
def dfs(row, col, graph, visited):
if 0 <= row < len(graph) and 0 <= col < len(graph[0]):
if graph[row][col] == 1 and (row, col) not in visited:
visited.add((row, col))
dfs(row - 1, col, graph, visited)
dfs(row + 1, col, graph, visited)
dfs(row, col - 1, graph, visited)
dfs(row, col + 1, graph, visited)def solution():
graph = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
]
count = 0
visited = set()
for row in range(len(graph)):
for col in range(len(graph[0])):
if graph[row][col] == 1 and (row, col) not in visited:
count += 1
dfs(row, col, graph, visited)
return countPath Finding: DFS is used to find a path between two vertices in a graph.
Connected Components: DFS is used to find the connected components in a graph.
Flood Fill: DFS is used to fill a region of a 2D array with a given color.
Backtracking: DFS is used in many backtracking problems such as the N-Queens problem, Sudoku solver, and more.
Graph Traversal: DFS is often used to traverse a graph and visit all the vertices in a graph.
Cycle Detection: DFS is used to detect cycles in a graph, which is an important problem in graph theory.
Topological Sorting: DFS is used to perform a topological sort of a directed acyclic graph (DAG), which is useful in many applications such as scheduling and task management.
경로찾기
연결요소
플러드필
백트래킹
그래프 순회
사이클 탐지
Path Finding
Connected Components
Flood Fill
Backtracking
Graph Traversal
Cycle Detection📘 응용④ 그래프 순회
📖 Graph Dictionary
from collections import deque
def dfs(graph, start_node):
visited = set() # set to keep track of visited nodes
stack = [start_node] # stack for DFS
while stack:
curr_node = stack.pop() # get the next node to visit
if curr_node not in visited:
visited.add(curr_node)
# Process current node here, e.g. print(curr_node)
# Add unvisited neighbors to stack
for neighbor in graph[curr_node]:
if neighbor not in visited:
stack.append(neighbor)📖 Graph 2D Array
📘 응용⑤ 사이클 찾기
📖 Graph Dictionary
📖 Graph 2D Array
꾸준히 노력하는 개발자