<그래프 알고리즘 BFS, DFS, 델타함수> 개인적인 정리

https://han-py.tistory.com/242

[코딩테스트] 쉽게 이해하고 바로 쓰는 DFS (깊이 우선 탐색)

 

그래프 알고리즘의 사실 핵심은 스택과 큐 인데 이를 자꾸 간과하는 느낌이 든다.

 

풀 때 마다 떠오르지 않아 고생하는 것들이 이렇게 두가지인 것 같다.

• 경우의 수를 어떻게 담을지, 어떻게 이어 나갈지를 생각할 때 항상 모든 경우의 수를 필요에 따라 스택 또는 큐로 기록해 두는 것이 중요한 것 같고.
• 델타함수를 이용할때는 visit 를 두어 방문여부를 항상 체크하고, 재귀함수를 이용해 경우의 수를 담아가는 아이디어가 중요한것 같다.

(예제?)

level 3 - 미로 탈출 명령어(kakao)

 

나는 문제의 특수한 상황 덕분에 그래프 알고리즘보다 델타함수를 이용한 그리디와 break 로 풀이를 했지만, 이를 원래방식대로 경우의 수를 stack을 쌓아가며 풀 수도 있었던 것 같다.

 

while과 queue 를 이용한 풀이

https://school.programmers.co.kr/questions/43761

프로그래머스

 

 

level 3 - 등대 (해결 못함)

(https://school.programmers.co.kr/learn/courses/30/lessons/133500)

 

재귀함수를 이용한 dfs 풀이

솔직하게 많이 놀랐던 풀이이다. 재귀함수를 통해 자식노드를 계속 호출하고 그 자식노드의 상태를 한번에 비트연산하여 부모노드를 업데이트 하는 방식, 그리고 return을 두개로 받아 상태를 계속 받아오는 형식이라던가, 상태에 따라 return을 갈라서 사용하는것 등이 좋은 방식이라 생각이 들었다. 

 

https://school.programmers.co.kr/questions/39676

 

 

 

 

 

 

 

 

아래는 내가 초기에(메모장으로) 정리해 뒀던 bfs, dfs, 델타함수 그래프 알고리즘을 정리해둔 내용이다.

 

그래프 알고리즘과 DFS, BFS

DFS는 수직적 BFS는 수평적 비교를 우선순위를 두어 고려하는 함수

DFS는 스택(stack)를 이용하고 BFS는 큐(Queue)를 이용한다

<DFS>

DFS란 말 그대로 깊이를 우선적으로 탐색하는 방법이다. 좀 더 쉽게 말하면, 갈림길이 있다면 한방향으로 끝까지 간 후에 답을 확인하는 과정을 반복한다. DFS는 스택(Stack)을 이용



def dfs(graph, start_node):
    visit = list()
    stack = list()

    stack.append(start_node)

    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])

    return visit


그러나!!
list를 통한 queue 는 시간복잡도가 O(N)으로 좋지 않음

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

 

 

<그래프 알고리즘을 통한 DFS 구현>

1.시작 정점의 한 방향으로 갈 수 있는 곳까지 깊이 탐색한다. (가면서 지나가는 것들을 하나씩 담는다)
2.가다가 더 이상 갈 곳이 없으면 가지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다.
3.다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문한다.
4.가장 마지막에 만났던 갈림길의 점점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용한다.


내가 생각하는 코딩 구성

1. 어느 노드에서 어느 노드로 이동할 수 있는지 파악

1) 인접행렬로의 표현 
(n+1) * (n+1) 행렬로 표현하여 노드끼리 이동할 수 있으면 1 없으면 0으로 표시

2) 델타함수의 표현
델타함수) 상 하 좌 우 로 이동할 수 있는 모든 경우의수를 한번씩 고려하도록 만드는 벡터
dx = [1,-1,0,0]
dy = [0,0,1,-1]

을 통해 
nx = x + dx[i]
ny = y + dy[i]
한칸씩 이동시키면서 계속 진행해나감

2. visited 배열, 벡터를 통해 방문여부를 파악하는 데 사용
- 한번 방문한 지역은 다시 들리지 않도록 계속 조건문으로 파악
if continue 함수를 사용하여 빠르게 패스시켜줌

3. 재귀함수를 통해 dfs 함수 내에서 계속 돌도록 반복.
조건을 만족한다면 계속 수직적으로 탐색하도록 재귀함수로 반복
-> 하나의 방향으로 더 진행할 수 없다면 함수안의 반복문을 통해 다음 이동을 탐색







<BFS>

 

BFS는 큐(Queue)를 이용

 

 

그래프와 시작 노드를 받아서 BFS 방식으로 그래프를 순회하는 함수이다.

(2~3) 방문했던 노드 목록을 차례대로 저장할 리스트와, 다음으로 방문할 노드의 목록을 차례대로 저장할 리스트(큐)를 만들어주자.

(5) 우선 맨 처음에는 당연히 시작 노드를 큐에 넣어준다.

(7) 큐의 목록이 바닥날때까지(더 이상 방문할 노드가 없을 때까지) loop를 돌려준다.

(8) 큐의 맨 앞에있는 노드를 꺼내온다.

(9) 해당 노드가 아직 방문 리스트에 없다면,

(10) 방문 리스트에 추가해주고,

(11) 해당 노드의 자식 노드들을 큐에 추가해준다.

from collections import deque

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

# 이 코드 안돼서 새로 짬

visited = []
queue = deque([list_[0][0]])
while queue :
    find_ = queue.popleft()
    visited.append(find_)
#     print('q : ',queue)
#     print('v : ',visited)
    for i in dic[find_] :
        if i not in visited :
            queue.append(i)

 

 

---

 

def bfs(graph, start_node):
    visit = list()
    queue = list()
    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit