[자료구조] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이우선탐색 (DFS)

0) 정의

-> Depth First Search의 약자로, 하나의 경우의 수에 대해 모든 경우의 수를 조사하고 다음 경우의 수를 조사하며 해를 찾는 과정

 

1) 구조

출처: encore 자료구조 강좌

 

2) 깊이우선탐색(DFS)과 스택

출처: encore 자료구조 강좌

· 시작점: A, A부터 검사 

· A가 정답이 아니므로, A 아래 가능한 경우의 수들을 모두 스택에 put 

· 스택에서 가장 위에 있는 B를 꺼내 (pop), B를 검사 

· B가 정답이 아니므로, B 아래 가능한 경우의 수들을 모두 스택에 put 

...

· 이 과정을 반복하며 정답 데이터를 찾음 

 

· 재귀를 통한 구현 

graph = {1:[2, 3, 4]. 2:[5], 3:[5], 4: [], 5:[6, 7], 6:[], 7: [3]}

def recursive_dfs(v, discovered = []):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered

· 반복문을 통한 구현 

def iterative_dfs(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]: 
                stack.append(w)
    return discovered

3) 응용 - 미로찾기

아래와 같은 미로가 주어질 때, 주어진 미로가 탈출 가능한 미로라면 True, 탈출 불가능한 미로라면 False 반환 

출처: encore 자료구조 강좌

· 해당 문제를 풀기 위해 갈 수 있는 길은 0, 갈 수 없는 길은 1로 표시하고, 스택을 선언 

· 처음 시작점인 (0,0) 검사 -> 도착 지점이 아니기 때문에, (0,0)에서 갈 수 있는 모든 경우의 수를 스택에 추가 

· (0,1) 지점 검사 -> 도착 지점이 아니기 때문에, (0,1)에서 갈 수 있는 모든 경우의 수를 스택에 추가 

· (0,2) 지점 검사 -> 도착 지점이 아니기 때문에. (0, 2)에서 갈 수 있는 모든 경우의 수를 스택에 추가 

... 이 과정 반복 

· (2, 3) 지점에서 더 이상 갈 수 있는 곳이 없음 -> 아무것도 추가 x 

· (1, 1) 지점 검사 -> 도착 지점이 아니기 때문에, (1, 1)에서 갈 수 있는 모든 경우의 수를 스택에 추가 

... 이 과정을 정답을 찾을 때 까지 반복. (5, 5) 지점에서는 도착 지점에 도착했기 때문에 True 반환 

위 로직을 코드로 구현해보자

while len(stack) > 0:
    now = stack.pop()
    if now == dest:   # 미로를 빠져나갈 수 있다면 
        return True
    x = now[1]   # 미로의 x 값 (왼쪽, 오른쪽) 
    y = now[0]   # 미로의 y 값 (위, 아래)
    if x - 1 > -1 :   # 왼쪽 방향으로 이동했을 때 인덱스 값을 벗어나지 않는다면 
        if maps[y][x-1] == 0:   # 갈 수 있는 길이라면 
            stack.append([y, x-1])
            maps[y][x-1] = 2  # 스택에 추가하고 방문 여부를 2로 표시 (방문 여부 표시 필수 !)
    if x + 1 < hori:
        if maps[y][x+1] == 0: 
            stacks.append([y, x+1]) 
            maps[y][x+1] = 2
    if y - 1> -1:   # 위로 이동할 수 있다면 
        if maps[y-1][x] == 0:
            stack.append([y-1, x])
            maps[y-1, x] = 2 
    if y + 1 < verti:
        if maps[y+1][x] == 0:
            stack.append([y+1, x])
            maps[y+1, x] = 2
    
    return False   # 스택에 데이터가 없을 경우

 

여기서 주의해야 할 것은, maps의 경우 2차원 배열로 행 * 열의 구조이기 때문에, now[x, y] 형태가 아닌 now[y, x] 형태로 생각해야 하는게 수월하다는 점 ! 

 

너비우선탐색 (BFS)

0) 정의

-> Breadth First Search의 약자로, 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정 

 

* BFS의 경우, DFS와 달리 재귀로 풀 수 없으며, 큐를 이용한 반복문을 통해서만 풀 수 있다. 

 

1) 구조

출처: encore 자료구조 강좌

2) 너비우선탐색(BFS)과 큐

출처: encore 자료구조 강좌

A를 시작으로 검사 

· A는 정답이 아니기 떄문에, A 아래 가능한 모든 경우의 수 (B, C, D)를 큐에 담는다.

· 큐는 선입선출의 구조.. 먼저 들어간 B를 검사 

· B는 정답이 아니기 때문에, B 아래 가능한 모든 경우의 수 (E, F)를 큐에 담는다.

... 

· 이 과정을 반복하며 정답 데이터를 찾음 

 

· 반복문을 통한 구현 

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

3) 응용 - 최단경로찾기

 

1번 섬에서부터 12번 섬까지 가는 최단 경로는 얼마인가 ? (단, 모든 경로의 거리는 1) 

출처: 엔코아 Data Structre 강좌

· 해당 문제를 풀기 위해 하나의 변수와, 큐를 선언해 줌 (큐에 있는 데이터들과 섬과의 거리를 알려주기 위한 변수) 

* 현재 큐에 있는 데이터들이 1번 섬과의 거리가 얼마인지를 나타냄

 

· 큐에서 데이터를 꺼냄 -> 거리 0의 개수 = 0, 다음에 들어올 데이터들 = 거리가 1인 섬 

· 데이터들을 큐에 집어넣음 

· 2번 섬을 꺼내어 검사, 2번 섬은 목적지가 아니므로 2번 섬에서 갈 수 있는 섬들 큐에 추가 

· 5번 섬을 꺼내어 검사, 5번 섬은 목적지가 아니므로 5번 섬에서 갈 수 있는 섬들 큐에 추가 

 · 6번 섬을 꺼내면 거리가 1인 섬들의 개수는 0이 되고, 큐에 존재하는 남은 섬들 = 거리가 2인 섬들이 됨

... 위 과정을 목적지를 찾을 때까지 반복. 12번을 꺼낼 경우, 우리가 원하는 목적지에 도착할 수 있음

위 로직을 코드로 구현해보자 

while len(queue) > 0:
    count = len(queue)   # 같은 거리에 있는 큐 데이터 갯수 
    for time in range(count):   # 같은 거리에 있는 큐 개수만큼 검사  
        now = queue.pop(0)
        if not == dest:
            return answer
        for i in data:   # 섬들간의 연결 리스트를 돌며 방문하지 않은 연결된 섬들만 큐에 추가 
            if i[0] == now and visited[i[1] - 1] == False:
                queue.append(i[1])
                visited[i[1] - 1] = True
            elif i[1] == now and visited[i[0] - 1] == False:
                queue.append(i[0])
                visited[i[0] - 1] = True
    answer += 1
return answer