TIL 2021/06/22 15일차

DFS

원소를 최대한 깊게 따라가며 탐색하는 방법

즉, 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,

가장 마지막에 넣은 노드들만 꺼내서 탐색하면 됨

가장 마지막에 넣은 노드들? → 스택을 이용하여 DFS를 재귀 없이 구현할 수 있다.

구현방법

1. 루트 노드를 스택에 넣는다.
2. 현재 스택의 노드를 빼서 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 2부터 반복한다.
5. 스택이 비면 탐색을 종료한다.

코드 구현

def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []
    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited

BFS

현재 인접한 노드 먼저 방문한다.

다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,

가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

가장 처음에 넣은 노드? → 큐를 이용하면 BFS를 구현할 수 있다.

구현방법

1. 루트 노드를 큐에 넣는다
2. 현재 큐의 노드를 빼서 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

코드 구현

def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []

    while queue:
        current_node = queue.pop(0)
        visited.append(current_node)
        for adjacent_node in adj_graph[current_node]:
            if adjacent_node not in visited:
                queue.append(adjacent_node)

    return visited

오늘 알고리즘...

백준 2630 색종이 문제에서 너무 많은 시간을 보냈다.

30분간 고민하고 그냥 찾아보려 했는데 될랑말랑 했던게 더 시간을 잡았먹었다.

찾아보니 global이라는 전역변수 설정을 안해서 그랬다....

이것도 파이썬 문법이 부족했던게 아닌가라는 생각이 들면서, 이런거였으면

시간을 너무 허비하지말고 진작 찾아볼거라는 생각이 들었다.

다시는 너무 시간을 허비하지말자......