DFS(Depth Fisrt Search) 깊이우선탐색으로 말 그대로 연결된 노드 트리를 따라 끝까지 탐색 후 다시 올라와 나머지를 탐색한다. 위와 같은 노드 트리를 탐색한다면 순서는 아마 [0, 1, 3, 4, 2]가 될 것이다. DFS를 재귀함수로 구현한 코드다. 함수에 함수가 쓰여 조건이 달성될 때까지 반복한다. BFS( Breadth First Search) 너비우선탐색으로 노드트리를 위에서 아래로 차례대로 탐색하는 특징을 갖고 있다. DFS와 달리 BFS로 위 노드 트리를 탐색하면 [0, 1, 2, 3, 4]의 순서를 가진다. 코드로 표현하면 아래와 같다. deque를 사용해 탐색할 노드의 맨 앞에서부터 가져오기때문에 아래에서 위로 순차적인 탐색이 가능하다. dfs, bfs의 특징을 이용해 풀 수 있는 문제가 나뉘기도하고 혹은 두 방법으로 동일한 문제를 풀 수도 있다.

백준 11725번 문제를 푸는데 계속해서 시간초과로 난항을 겪고 있었다. 이 문제를 풀기 위해 내가 짠 코드는 다음과 같다. 파이참에서 실행시켰을때는 입출력 예제와 똑같이 나왔기에 이제 여기서 줄일 만한 곳을 찾기 시작했다. graph를 딕셔너리로 만들었는데 리스트로 변경하면 좀 더 시간이 줄어들까 싶어 시도했지만 역시나 실패였다. 그후 몇 가지 시도를 하다보니 코드가 아예 틀리기도 했다. 결국 나는 그를 찾아갔다. 거의 솔루션은 간단했다. 리스트(list)를 세트(set)로 변경하는 것이다. 위 코드 중 일부를 보면 입력값을 받아 그래프를 만든 후 부모 노드를 찾기 위해 bfs를 사용했다. def bfs_queue(start): parent = [0] * (n+1) visited = [start] q = deque([start]) while q: node = q.popleft() for adj in graph[node]: if adj not in visited: parent[adj] = node q.append(adj) visited.append(adj) def bfs_queue(start): parent = [0] * (n+1) visited = set([start]) q = deque([start]) while q: node = q.popleft() for adj in graph[node]: if adj not in visited: parent[adj] = node q.append(adj) visited.add(adj) visited는 방문한 노드를 중복 방문하지 않기 위해 만든 리스트다. if문에 인접 노드가 이미 visited에 없다면 아래 코드를 반복해서 실행한다. 이때 if adj not in visited의 시간 복잡도는 O(n)이다. 하지만 visited를 세트(set)로 바꾸면 시간 복잡도는 O(1)이 된다. 리스트와 세트의 연산 차이점을 나타낸 표를 참고해보면, 리스트(list)