알고리즘 템플릿 정리

백트래킹, BFS, DFS, 암시적BFS, 암시적DFS, 다익스트라, 위상정렬, DP

 

백트래킹

• 트리 구조를 그려보고 반복되는 부분을 for문에 구성 (추가 반복이 필요하면 함수 밖도 고려)
• 큰 구조는 base case와 repeat
• 만약 중간에 탈출하려면 base case에 return을 해주고 함수를 아예 끝내려면 함수 호출을 하면서 return
•  append-backtracking()-pop은 하나의 세트 (append를 했으면 pop을 해야하고, backtracking에 바로 넣으면 상관 없음)
• backtracking 인자에 다른 것도 넣을 수 있다. 

nums = [1, 2, 3, 4, 5]
output = []

def backtracking(curr):
    # base case
    if len(curr) == len(nums):
    	output.append(curr[:])
    # repeat
    for num in nums:
    	if num not in curr:
            curr.append(num)
            backtracking(curr)
            curr.pop()
            
backtracking([])

 

 

 

BFS

def bfs(graph, start_v):
    from collections import deque
	q = deque()
	q.append(start_v)
	visited = {start_v: True} #방문 표기하여 중복 방지
	
	# q가 비어있을 때까지 예약된거 처리하고, 다음 방문 예약하고 반복
	while q:
        # 방문
        cur_v = q.popleft()
        # 인접 리스트에서 현재 cur_v와 연결되어 있는 모든 next_v를 하나하나 (방문확인 및 예약) 체크
        for next_v in graph[cur_v]:
            if next_v not in visited:
                q.append(next_v)
                visited[next_v] = True
				
graph = {
	0: [1, 3, 6],
	1: [0, 3],
	2: [3],
	3: [0, 1, 2, 7],
	4: [5],
	5: [4, 6, 7],
	6: [0, 5],
	7: [3, 5],
}
bfs(graph, start_v=0)

 

 

 

DFS

def dfs(cur_v):
    visited[cur_v] = True
    for next_v in graph[cur_v]:
        if next_v not in visited:
            dfs(next_v)
            
visited = {}
graph = {
	0: [1, 3, 6],
	1: [0, 3],
	2: [3],
	3: [0, 1, 2, 7],
	4: [5],
	5: [4, 6, 7],
	6: [0, 5],
	7: [3, 5],
}
dfs(0)

 

 

 

 

암시적 그래프 BFS

• bfs()를 실행하면 현재 위치에서 조건에 따라 연결된 노드를 모두 탐색한다. (가까운것부터)
• 추가 방문 조건, 방향 등 주어진 조건에 따라 수정하면 된다. 
• 조건을 만족하면 'append, visit, graph' 까먹지 말자. 

def solution(grid):
    from collections import deque 
    row_len = len(grid)
    col_len = len(grid[0])
    visited = [[False for _ in range(col_len)] for _ in range(row_len)]
    
    def bfs(r, c):
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]
        visited[r][c] = True
        q = deque()
        q.append((r, c))
        
        while q:
            cur_r, cur_c = q.popleft()
            for i in range(4):
                next_r = cur_r + dr[i]
                next_c = cur_c + dc[i]
                if 0 <= next_r < row_len and 0 <= next_c < col_len:
                    if visited[next_r][next_c] == False:
                        q.append((next_r, next_c))
                        visited[next_r][next_c] = True
    bfs(r, c)

 

 

 

 

암시적 그래프 DFS

• dfs()를 실행하면 현재 위치에서 조건에 따라 연결된 노드를 모두 탐색한다. (연결된것부터)
• 추가 방문 조건, 방향 등 주어진 조건에 따라 수정하면 된다. 

def solution(grid):
    row_len = len(grid)
    col_len = len(grid[0])
    visited = [[False for _ in range(col_len)] for _ in range(row_len)]
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    
    def dfs(cur_r, cur_c):
        visited[cur_r][cur_c] = True
        for i in range(4):
            next_r = cur_r + dr[i] 
            next_c = cur_c + dc[i]
            if 0 <= next_r < row_len and 0 <= next_c < col_len:
                if visited[next_r][next_c] == False:
                    dfs(next_r, next_c)
    dfs(r, c)

 

 

 

 

다익스트라