DFS & BFS

😆 동빈나 님의 이코테 2021 강의 몰아보기를 보면서 공부한 내용을 정리하고 있습니다. 책은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 학습했습니다.😊

---

‏‏‎ ‎

⚽그래프 탐색 알고리즘 : DFS/BFS

탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정!

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.

DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지!!

DFS/BFS 시작하기 전에 반드시 알아야할 자료구조는 스택, 큐

먼저 스택 자료구조에 대해 공부해보자.

✈️스택 자료구조

먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

입구와 출구가 동일한 형태로 스택을 시각화하자!

파이썬에서 스택을 이용하기 위해서 리스트 이용하면 돼

가장 오른쪽에 원소를 삽입하는 append()함수와 가장 오른쪽에 원소를 삭제하는 pop()함수를 이용해서 스택처럼 사용할 수 있어

스택에 담겨있는 원소를 출력할 때 스택의 최상단에서부터 출력한다면 현재 스택이 리스트 형태로 구현되어 있기 때문에 리스트에 담긴 원소를 거꾸로 출력하면 돼!

print(stack[::-1]) → 이렇게 하면 돼! 최상단 원소부터 출력! -- 스택을 차례차례 pop하는것과 같음

print(stack) --> 최하단 원소부터 출력

---

큐 자료구조에 대해서 공부해보자

✈️큐 자료구조

먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조

큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화!

즉, 앞에서 삽입해주고 뒤에서 삭제해주면 돼! → 파이썬에서 공간을 효율적으로 사용하기 위해 큐를 구현할 때는 리스트가 아닌 데크를 사용하자.

파이썬에서 큐를 사용할 때는 데크(deque) 라이브러리 사용!!!

append()함수는 리스트에서 동작과 동일. 마지막에 삽입해!!

popleft()함수는 가장 왼쪽에 있는 데이터를 꺼낼때 사용 -- 먼저 들어와있는 데이터는 앞에서부터 채워지잖아.

---

💦 DFS를 공부하기 전에 재귀함수에 대해서 확실하게 알고 넘어가기

🎃재귀함수

재귀함수(Recursive Function)는 DFS를 구현할 때 자주 사용하는 방법 중 하나야!
(거의 대부분)

🎈항상 종료조건을 먼저 생각하자!

---

<앞에서 공부한 내용을 바탕으로 이제 DFS에 대해서 알아보자>

⚽DFS : 깊이우선탐색

스택자료구조 혹은 재귀함수를 이용한다.

재귀함수로 탐색하거나 문제를 푼다고 할 때, 함수 이름을 dfs로 해서 풀자

• 구체적인 동작과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
  3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼내
  4. 더이상 2번 과정을 수행할 수 없을때까지 반복한다.

탐색시작노드를 인자로 주기!

어디서부터 방문하든 상관없어! 그래도 번호가 낮은 인접노드부터 준비하자

방문처리하고(visited[v] = 1) 스택에 삽입했으니(DFS(v)) 인접노드 확인해야해

그래프를 이차원 리스트로 준비하고, 해당 노드의 값이 바로 인접노드겠네

방문하지 않은 인접노드 중에서 노드 값이 작은 노드부터 방문해!!!!

더이상 들어갈 곳이 없다면 돌아와서 다시 방문하지 않은 노드가 있는 곳으로 돌아갈꺼야! (백트랙킹)

스택에 삽입하고 방문처리해서 들어가서 인접노드가 없다 ? 그럼 이제 스택에서 꺼내는거야

방문하지 않은 인접노드가 있기 떄문에 다시 스택에 넣고 방문처리!

⚽전체노드의 탐색 순서는 스택에 들어간 순서이다.

🧨파이썬으로 DFS구현하기

파이썬에서는 그래프를 표현하기 위해 2차원리스트를 사용해!

일반적으로 그래프 문제가 출제되면 노드의 번호가 1번부터 출발하는 것이 많기 떄문에 인덱스 0번에 대해서는 비워두고 1번 인덱스부터 해당 노드의 인접한 노드가 무엇인지 리스트 형태로 담아줄 수 있어!

즉 위와 같이 1번 노드와 인접한 노드는 2,3,8번이라고 리스트를 초기화한 것을 확인할 수 있음!

→방문처리를 위해 하나의 1차원 리스트 필요! -- 기본값을 False로 해서 모두 방문하지 않은 것으로 처리하고 시작

🚀 인덱스 0을 사용하지 않는 방식을 이용하는게 문제에서 나와있는 노드의 번호를 그대로 인덱스 형태로 맵핑할 수 있기 때문에 더 헷갈리지 않고 직관적일 수 있어!

⚽dfs함수 코드 직접 짜보기

#DFS 소스코드  -- DFS 메서드 정의
def dfs(graph, v, visited):   #그래프의 정보, 방문처리할 리스트 이용 리스트는 굳이 인자로 안넣어줘도 되긴 하다.
    #현재 노드를 방문처리
    visited[v] = True
    print(v, end = " ")
    #현재 노드와 연결된 다른 노드들 재귀적으로 방문
    for i in graph[v]:   #graph[v]는 현재 노드 v의 인접한 노드들 하나씩 꺼내서 확인할꺼야!!
        if visited[i] == False:  #인접한 노드 방문하지 않았다면 방문해야지 --> if not써도 됨
            dfs(graph, i, visited)

#각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [], 
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
#각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9  #인덱스 1부터 할꺼라 한개 더!
#정의된 DFS함수 호출
dfs(graph, 1, visited)

⚽ 항상 해당 노드를 방문하는 순간 현재 방문한 노드를 방문처리 먼저 해주는거 잊지말자!

---

⚽ BFS : 너비우선탐색

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용하며 동작 과정에 대해 알아보자.
  1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
• (최단거리 구하는 문제에서 자주 사용된다.) → 이 유형으로 자주 사용 돼!!!
• 동작예시

BFS는 해당시점에서 인접한 노드를 한번에 전부 큐에 넣는다는 것이 특징!

• 특히 BFS 알고리즘은 특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로도 효과적으로 사용

작은 노드부터 넣을꺼야!

전체 노드의 탐색 순서 : 큐에 들어간 순서

파이썬에서 BFS코드는 큐를 위해 deque 라이브러리 선언!

DFS때와 마찬가지로 0번 인덱스는 사용하지 않아

BFS 소스코드

#BFS메서드 정의
def bfs(graph, start, visited):  #시작노드를 큐에 넣어줘
    #큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])   #데크로 변환할 때 리스트화 해주고 했어야!!
    #현재 노드를 방문 처리
    visited[start] = True
    #큐가 빌 때까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()   
        print(v, end = " ")
        #아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:   #graph[v]는 현재 노드의 인접한 노드들의 리스트!
            if visited[i] == False: #방문하지 않은 노드라면!
                queue.append(i)
                visited[i] = True #큐에 넣어준 후 방문처리 해주면 돼!

#각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [], 
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
#각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9  #인덱스 1부터 할꺼라 한개 더!
#정의된 DFS함수 호출
bfs(graph, 1, visited)

---

⚽ DFS & BFS 문제 풀어보기

이 문제는 서로 연결요소 개수가 몇개인지 구하면 돼!

⚽ 연결요소 개수 구하기 - DFS, BFS (모두 가능)

• :연결요소 개수 구하는 문제는 결국 DFS, BFS 둘 중 어떤 걸로든 풀 수 있다.

즉 인접한 노드의 형태로 그래프 유형의 문제라는거 파악했어야해 → (DFS BFS로 풀 수 있겠다..? 까지 캐치하고 진행하자)

1로 처리되어 있는 칸은 인접하지 않아서 방문처리되지 않을꺼야

방문처리가 이루어지는 요소에 대해서만 카운팅하면 된다.

방문한 지점에서 다시 상하좌우를 살피고 방문을 진행하는 과정을 반복하는 것이 핵심 !

음료수 얼려먹기 해당문제 소스코드

#음료수 얼려먹기
N, M = map(int, input().split())
#DFS로 특정 노드를 방문하고 연결된 모든 노드들(인접한 노드)도 방문
def dfs(x,y):
    #주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x>=N or y <= -1 or y >=M:   #2차원 리스트 범위 벗어나는 경우
        return False   
    #현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        #해당 노드 방문 처리
        graph[x][y] = 1 
        #상하좌우 위치들도 모두 재귀적으로 호출  --> 연결지점은 모두 방문처리 하네
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False   #이미 방문했으면 False 리턴

#2차원리스트 의 맵 정보 입력받기
# graph = []
# for i in range(N):
#     graph.append(list(map(int, input().split)))
graph = [list(map(int, input().split())) for i in range(N)]  #간단하게 2차원 리스트 만들기

#모든 노드(위치)에 대해서 음료수 채우기
result = 0
for i in range(N):
    for j in range(M):    #NxM 2차원에서 수행.
        #현재 위치에서 DFS수행
        if dfs(i, j) == True:  #dfs한번 수행하면 해당 노드와 연결된 모든 노드들도 방문처리 할 수 있도록함!!
            result +=1 #해당 노드만 방문처리 되면 +1
        #i,j한번 방문하면 인접한 노드들은 모두 방문처리 되잖아! 그래서 카운팅 한번만 돼!!!!
print(result)

• 이 문제처럼 0,1 로 해당 그래프를 구분할 수 있다면 따로 방문 체크 리스트가 필요하진 않아. 그 안에서 1로 다시 칠해주면 되기 때문 !!

---

🎈 미로탈출문제

이 문제를 해결하는 키워드

값이 1인 노드로만 이동이 가능하다고 판별하여 최단거리 구할 수 있어!

그 이유는 시작위치와 마지막 위치까지의 노드를 포함되어야 해!

매번 새로운 지점을 방문할 때 그 이전 지점까지의 최단거리에 +1을 해서 기록!

결국 마지막위치에 기록되어 있는 최단거리 값을 출력하도록 만들면 정답 판정을 받을 수 있어!!

🎈 ‏‏‎ ‎미로탈출문제 소스코드

#미로탈출 문제
from re import A
import heapq as hq            #힙큐! 쓰겠다는 소리
from collections import deque  #데크를 사용하기 위해 라이브러리 선언!
import sys
sys.stdin = open("input.text", "rt")

#이 문제 역시 행, 열을 축소 시켜서 내가 이해할 수 있는 환경으로 만들고 어떻게 구동되는지 예측해보면서 풀어보는게 좋다! 3x3으로 만들어서 어떻게 하면 될까? 를 생각해봤어야함!!!
#미로탈출 NxM
#(1,1) 시작, 출구 (N,M) 한번에 한칸씩
#괴물이 있는 곳 0 괴물이 없는 곳 1로 표시
#탈출하기 위해 움직여야 하는 최소 칸의 개수 구하기
# 이 문제는 BFS!! BFS는 간선의 비용이 같을 때 최단거리를 탐색하기 위해 사용할 수 있는 알고리즘이야!
#시작지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문!
#이때 상황적으로 연결된 모든 노드는 이동이 가능하기 때문에 거리가 1로 동일
#가장 왼쪽 위 지점의 (1,1)에서 bfs를 수행해서 모든 노드에 대한 최단거리 값을 기록하는 방식으로
#알고리즘을 작성하면 문제 해결 가능
N, M = map(int, input().split())
graph = []   #이 문제가 왜 그래프 문제인지 생각 --> 인접한 위치의 정보 때문..?
for i in range(N):
    graph.append(list(map(int, input()))) #문자열로 숫자 입력한거 전부 정수로 바꿔서 리스트화! 이러면 각각의 숫자를 인덱스로 접근가능

#1인곳만 이동할 수 있잖아. 이동할 방향 필요
#이동할 네 가지 방향 정의(상 하 좌 우) --> 방향벡터 정의!
dx = [-1,1,0,0]
dy = [0,0,-1,1]

#BFS 소스코드 구현
def bfs(x,y):  #행 열   ,   bfs는 큐 사용해야 하는거 잊지말고
    #큐(queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y)) #x,y의 튜플 데이터 추가  처음 x,y는 0,0 즉 행열의 위치를 통해...
    #큐가 빌 때까지 반복
    while queue:
        x,y = queue.popleft()
        #현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #미로 찾기 공간을 벗어난 경우 무시. 즉 인덱스 오류인 경우
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            #괴물이 있는 곳인 경우 무시
            if graph[nx][ny] == 0:
                continue
            #해당 노드를 처음 방문하는 경우에만 최단 거리 기록.
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1  #바로 직전 노드에서의 최단거리 값에 1을 더해
                queue.append((nx,ny))  #이걸 추가!
        
        #가장 오른쪽 아래까지의 최단 거리 반환
    return graph[N-1][M-1]

#BFS를 수행한 결과 출력
print(bfs(0,0))

‏‏‎ ‎

---

⚽ 추가적으로 DFS/BFS 내용 및 마인드셋 정리

DFS에서는 깊이우선! 즉 더이상 들어갈 수 없는 말단노드까지 먼저 가는 구조였는데

BFS는 넓이우선 탐색! → 레벨 탐색을 해

이진트리를 통해 이해해보자

0레벨에서 한번 만에 갈 수 있는 것들. 즉 1레벨의 노드들 (바로 이동할 수 있는 곳으로 이동)

2레벨 애들은 0번에서 2번만에 가잖아

0레벨 -> 1레벨 -> 2레벨 -> .... 이런 식으로 방문을 진행

BFS를 구현 하려면 큐를 통해 구현해! 먼저 들어간게 먼저 나와.

최초의 큐에 루트노드 0번을 넣고 시작해! (루트노드 pop() 하면서 시작하는게 BFS)

그리고 0번을 pop해서 나오면 0번과 연결된 한번의 간선으로 갈 수 있는 노드들(인접노드)을 모두 큐에 넣기(큐에 들어갔다면 탐색이라고 봐야해)

연결된걸 다 넣었다면 큐에서 pop하나 해서 그 노드와 연결된 한번의 간선으로 갈 수 있는 노드들(인접노드)을 다시 큐에 넣어! 다 넣었으면 또 pop해서 다시...이 과정 반복해!!!!

물론 재방문 하지 않기 위해서 중복을 방지하는 리스트 필요해

왜냐면 계속 한번만에 갈 수 있는 노드들을 계속 추가하면 무한루프에 빠지기 때문!

DFS/BFS 문제는 상태트리가 어떻게 뻗어나가는지를 잘 파악하면 문제를 푸는데 어려움이 없을꺼야