from collections import deque

 

디큐는 속도가 빠른 리스트로 생각해도 좋다.

 

코딩 테스트에서 파이썬으로 Queue, BFS, FIFO 방식의 알고리즘 접근이 필요할 때 리스트를 디큐로 바꾸어주면 속도 이슈 해결이 가능하다.

 

a_list = [1, 2, 3, 4, 5]
# [1, 2, 3, 4, 5]

a_dq = deque(a_list)
# deque([1, 2, 3, 4, 5])

 

이렇게 간단하게 디큐 함수로 바꾸어주기만 하면 된다.

 

a_dq.pop()
a_dq.popright()
# 5

a_dq.popleft()
# 1

a_dq
# deque([2, 3, 4])

a_dq.append(1004)
# deque([2, 3, 4, 1004])

 

  • 디큐 맨 마지막 값을 뺄 때 : .pop()
  • 디큐 맨 처음 값을 뺄 때 : .popleft()
    • 주의 / .pop(0)과 같이 사용하면 에러 발생!
  • pop과 popleft 모두 기존의 디큐를 수정, 업데이트하는 파괴적 함수!
  • 디큐 맨 뒤에 값을 추가할 때 : .append()

 

디큐를 활용한 bfs

graph_list = [
    [],
    [2,3,8], 
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]


def bfs(graph, start):
    need_visit = deque([])
    visited    = deque([])
    need_visit.append( start )
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            temp = graph[node]
            temp_reverse = list(reversed(temp))
            need_visit.extend( temp_reverse )
    return visited
    
    
  bfs(graph_list, 1)
  # deque([1, 8, 3, 2, 7, 5, 4, 6])

'Code > algorithm' 카테고리의 다른 글

알고리즘 | BFS 활용하여 미로 찾기 문제 풀기  (0) 2024.04.01
알고리즘 | BFS 활용하여 특정 도시 거리 계산 문제 풀기  (0) 2024.04.01
알고리즘 | 정렬 (선택정렬/삽입정렬/버블정렬)  (0) 2024.04.01
알고리즘 | 탐색 기본 - Stack, Queue  (0) 2024.04.01
알고리즘 | 탐색 기본, 인접행렬과 인접리스트  (0) 2024.04.01

 

엣지를 따라 모든 노드를 방문하는 것을 그래프 탐색이라고 한다.

대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다.

 

 

Depth First Search (깊이 우선 탐색)

깊이 우선 탐색은 기본적으로 Stack이다. (Last In First Out)

오른쪽 왼쪽 상관은 없음

 

예제

graph_list = [
    [],        # 0번 도시(없음)
    [2, 3, 8], # 1번 도시
    [1, 7],    # 2번 도시
    [1, 4, 5], # 3번 도시
    [3, 5],    # 4번 도시
    [3, 4],    # 5번 도시
    [7],       # 6번 도시
    [2, 6, 8], # 7번 도시
    [1, 7]     # 8번 도시
]
 

1번 도시 방문
  • To do : [2, 3, 8]
    • 2번 도시 방문
    • To do : [1, 7] -> 1번은 됐고 7번 방문
      • To do : [2, 6, 8] -> 2번은 됐고 6번 방문
        • To do : [7] / 끝!
        • 8번 방문 / 끝!
    • 3번 도시 방문
    • To do : [1, 4, 5] -> 1번은 됐고 4번 방문
      • To do : [3, 5] -> 3번은 됐고 5번 방문 / 끝!
Done = [1]

Done = [1, 2]

Done = [1, 2, 7]

Done = [1, 2, 7, 6]

Done = [1, 2, 7, 6, 8]

Done = [1, 2, 7, 6, 8, 3]

Done = [1, 2, 7, 6, 8, 3, 4]

Done = [1, 2, 7, 6, 8, 3, 4, 5]

예제 문제 DFS 코드(함수)로 구현하기

graph = [
    [], #0
    [2, 3, 8], #1
    [1, 7], #2
    [1, 4, 5], #3
    [3, 5], #4
    [3, 4], #5
    [7], #6
    [2, 6, 8], #7
    [1, 7], #8
]

def dfs(graph, start_city) :
    to_visit = graph[start_city]
    done_visit = [start_city]

    while to_visit:
        visited = to_visit.pop()
        if visited not in done_visit:
            done_visit.append(visited)
            to_visit.extend(graph[visited])

    return done_visit

dfs(graph, 1)
>>> [1, 8, 7, 6, 2, 3, 5, 4]
 

pop으로 꺼내서 할당하는 visited의 값이 가장 큰 숫자부터 고르기때문에 [1, 8, 7, 6, 2, 3, 5, 4]가 나온다. 예제 문제처럼 pop으로 꺼내는 도시가 가장 작은 숫자부터 고르게 하려면 어떻게 해야 할까?

def dfs_2(graph, start_city) :
    to_visit = list(reversed(graph[start_city])) #💛
    done_visit = [start_city]
    while to_visit:
        visited = to_visit.pop()
        if visited not in done_visit:
            done_visit.append(visited)
            temp = graph[visited] #💛
            temp_reversed = list(reversed(temp)) #💛
            to_visit.extend(temp_reversed) #💛
    return done_visit

dfs_2(graph, 2)
>>> [1, 2, 7, 6, 8, 3, 4, 5]
 

뒤집어서 맨 뒤부터 추가해주기!

 

 

 

BFS의 경우 pop()을 pop(0)으로 변경해주면 끝인데,

속도 이슈가 있기때문에 코딩테스트에 권장하지 않음

-> 너비 우선 탐색법이 필요한 경우 depop을 고려

 

'Code > algorithm' 카테고리의 다른 글

알고리즘 | BFS 활용하여 특정 도시 거리 계산 문제 풀기  (0) 2024.04.01
알고리즘 | queue(FIFO) 속도이슈를 해결할 수 있는 deque  (0) 2024.04.01
알고리즘 | 정렬 (선택정렬/삽입정렬/버블정렬)  (0) 2024.04.01
알고리즘 | 탐색 기본 - Stack, Queue  (0) 2024.04.01
알고리즘 | 탐색 기본, 인접행렬과 인접리스트  (0) 2024.04.01

+ Recent posts

티스토리툴바