이것이 코딩 테스트다 - Chapter5 DFS, BFS 정리

 

"DFS, BFS" 이란

그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

 

여기서 탐색이란 "원하는 데이터를 찾는 과정"을 말하기에

그래프 탐색이란 "그래프 내에서 원하는 데이터를 찾는 과정"을 일컬는다.

 

여기서 기초적으로 그래프 탐색 전에 알아야 하는 자료구조 개념이 필요하다.

 

1. 스택 Stack

스택은 선입후출 구조로 쌓이는 구조라 생각하면 된다. 

재귀함수에서 사용되며, 재귀함수는 DFS에서 사용된다.

 

2. 큐 Queue

큐는 선입선출 구조로 차례로 들어온대로 나가는 구조라 생각하면 된다.

BFS에서 사용된다.

 

3. 재귀함수 Recursive function

재귀함수는 함수가 함수를 다시 부르는 경우이다.

보통 연쇄적으로 계산되는 경우 종료조건을 만족할때까지 재귀가 이뤄지다가 다시 반환되며 종료되는 식이다.

 

이렇게 세가지 개념이 있다.

다음으로는 각 개념을 간단하게 구현한 코드를 살펴보겠다.

 

1.  스택 Stack

stack = []
stack.append(5) #5
stack.append(2) #52
stack.pop()     #5

append, pop 명령어를 통해 넣고 뺀다.

stack.reverse()

reverse 명령어를 통해 순서를 바꿀 수 있다.

 

2. 큐 Queue

from collections import deque
queue = deque()

queue.append(5) #5
queue.append(2) #52
queue.popleft() #2

from collections import deque를 통해 import 작업이 필요하다.

append, popleft 명령어를 통해 넣고 뺀다.

queue.reverse()

reverse 명령어를 통해 순서를 바꿀 수 있다.

 

3. 재귀함수 Recursive function

def recursive_function(i) :
  #1. 재귀 종료조건 명시
  if i == 5 : 
    return
  #2. 함수기능
  print(i,'번째 재귀 함수에서',i+1,'번째 재귀함수를 호출합니다.') 
  #3. 재귀 호출
  recursive_function(i+1) 
  #4. 재귀 완료 후 함수기능
  print(i,'번째 재귀 함수를 종료합니다.')

recursive_function(1)

1. 재귀 종료조건

2. 함수 기능

3. 재귀 호출

4. 재귀 종료 후 함수기능 (재귀 호출이 return 값인 경우 생략된다)

 

위 순서를 토대로 작성이 된다.

 

 

 

이렇게 지금까지 DFS, BFS 탐색을 위한 기초 자료구조인 "스택", "큐", "재귀함수"를 정리하였다.

다음으로는 "그래프를 표현하는 방법" 두가지를 살펴보겠다.

 

1. 인접 행렬

N개의 데이터가 있으면 N✕N 크기의 2차원 배열로 저장하는 구조이다.

저장되는 값은 두 노드를 연결하는 간선의 크기이며 연결여부만 필요하면 1로 저장된다.

INF = 999999999
graph = [
  [0,7,5],
  [7,0,INF],
  [5,INF,0]
]

장점 : 속도가 빠르다(크기가 고정되어 있는 경우)

단점 : 메모리가 비효율적 (O(N^2))

 

2. 인접 리스트

각 노드에 대해서 인접된 노드를 리스트로 나열한 구조이다.

(node, value)의  형태로 인접 node 와 간선의 크기를 저장한다. 연결여부만 필요하면 value 없이 node 값만 저장된다.

graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))

장점 : 메모리가 효율적 (O(N+M))

단점 : 속도가 비교적 느리다

 

 

이렇게 두가지 형식으로 그래프를 표현할 수 있다.

다음으로는 이제 "그래프 탐색 방식인 DFS, BFS"를 살펴보겠다.

 

1. DFS 깊이 우선 탐색 (Depth First Search)

방문이 가능한 만큼 계속하여 방문한다.

방문이 불가능한 경우 이전 노드로 이동하여 다음 방문을 실시한다.

 

보통 "미로찾기" 개념으로 사용된다. 즉,

특정한 조건이 될때까지 탐색을 하는 경우에 사용된다.

보통 스택에 넣은 뒤 해당 노드의 인접노드 중 방문하지 않은 노드를 다시 스택에 넣는식으로 구현한다.

하지만 스택을 대신하여 재귀함수가 더 많이 사용된다.

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

visited = [False]*9

def dfs(graph, v, visited) :
  visited[v] = True
  print(v, end=" ")

  for i in graph[v] :
    if not visited[i] :
      dfs(graph, i, visited)

인접리스트로 표현된 그래프를 재귀함수를 통해 DFS를 구현하였다.

인접리스트에서 방문안된곳이 있는경우 재귀를 통해 방문한다.

 

다음으로는 DFS를 활용한 예시문제를 보겠다.

 

N, M을 입력받아 N✕M 크기의 얼음틀이 입력된다. 이때 칸막이는 1이며 빈칸은 0이다.

빈칸이 상하좌우 방향으로 붙어있는 경우 하나의 얼음이 된다. 이때, 총 얼음의 수를 구하여라.

 

이 경우, 특정한 조건이 될때까지(인접 빈칸이 있는지 여부) 탐색을 하는 경우이다. 따라서 DFS 방식이 사용된다.

graph = []
def dfs(x,y) :
  #1. 재귀 종료조건 - 범위를 벗어나는 경우
  if x<0 or x>N-1 or y<0 or y>M-1 : 
    return False
  
  #2. 함수 기능 - 빈칸의 경우 방문처리한다.
  if graph[x][y] == 0 :
    graph[x][y] = 1
    
    #3. 재귀 호출 - 사방을 확인한다.
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y+1)
    dfs(x,y-1) #사방을 재귀로 확인한다
    
    #4. 재귀 종료 후 함수 기능 - 재귀가 끝나는 시점은 빈칸을 다찾은 경우이므로 함수를 종료한다.
    return True
  else :
    return False

N, M = map(int, input().split())
for i in range(1,N+1) :
  temp = list(map(int, input()))
  graph.append(temp)

result = 0
for i in range(N) :
  for j in range(M) :
    if dfs(i,j) == True : #0이 있는경우 1로 변경을 거친 후 얼음개수를 증가한다
      result += 1

print(result)

2차원 배열로 (인접행렬) 입력받아

빈칸인 경우 사방또한 빈칸인지 재귀로 확인 후 빈칸덩어리가 구해지면 반환하는 구조이다.

 

 

다음으로 BFS를 살펴보겠다.

 

2. BFS 너비 우선 탐색 (Breath First Search)

인접한 노드들 중에 방문가능한 노드 전부로 퍼지면서 찾는다.

방문이 불가능한 경우 종료된다.

 

보통 "최단경로"를 구할 때 사용된다. 즉,

끝점까지 가는 최단경로를 구하는 경우에 사용된다.

인접노드 전부 방문하며 차례로 범위가 넓혀지는 구조이므로 큐를 사용한다.

시작점을 큐에 넣고서 반복문을 통해 차례로 큐에서 제거하며 방문처리 후 인접노드들을 큐에 넣는 식으로 구현된다.

 

from collections import deque

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

visited = [False]*9

def bfs(graph, start, visited) :
  queue = deque([start])
  visited[start] = True
  
  while queue :
    #값에 접근한다.
    v = queue.popleft()
    print(v, end=" ")

    #인접 노드들 중 방문가능한 노드의 경우 방문처리 후 큐에 넣는다.
    for i in graph[v] :
      if not visited[i] :
        visited[i] = True
        queue.append(i)
        

인접리스트로 표현된 그래프를 큐와 반복문을 통해 BFS를 구현하였다.

큐에서 값을 하나씩 제거하며 방문을 완료한 뒤, 인접리스트에서 방문안된곳이 있는경우 큐에 넣는다.

반복문을 통해 큐가 빌때까지 계속한다.

 

다음으로는 BFS를 활요한 예시문제를 보겠다.

 

N, M을 입력받아 N✕M 크기의 미로가 입력된다. 이때 길은 1이며 장애물은 0이다.1,1 위치에서 N,M까지 갈수있는 길이 있으며, 이 길의 최소한의 칸의 개수를 구하여라. (시작, 종료 칸을 포함한다)

 

이 경우, 끝점까지(N,M) 최단경로(칸의 수)를 구하는 경우이다. 따라서 BFS 방식이 사용된다.

 

from collections import deque
graph = [] #게임저장
move = [(-1,0), (1,0), (0,-1), (0,1)] #이동을 위한 리스트

N, M = map(int, input().split())
for i in range(N) :
  graph.append(list(map(int, input())))

def bfs() :
  queue = deque()
  #시작점 추가
  queue.append((0,0)) 
  
  #반복문을 통해 큐에 넣고 빼는 과정을 반복한다.
  while queue :
  
    #하나를 제거하며 값에 접근한다 - 다음위치로 이동가능여부 확인
    x, y = queue.popleft()
    for i in range(4) :
      next_x = x+move[i][0]
      next_y = y+move[i][1]

      #위치를 벗어나는 경우 다음반복을 실행한다.
      if next_x<0 or next_x>N-1 or next_y<0 or next_y>M-1 :
        continue 
      #장애물의 경우 다음반복을 실행한다.
      if graph[next_x][next_y] == 0 :
        continue
        
      #길의 경우 현재위치의 숫자+1로 다음위치 값을 변경 후 큐에 넣는다.
      if graph[next_x][next_y] == 1 :
        graph[next_x][next_y] = graph[x][y]+1
        queue.append((next_x, next_y))
        continue

bfs()
print(graph[N-1][M-1]) #최종적으로 적힌 숫자를 반환한다

2차원 배열로 (인접행렬) 입력받아 

사방으로 이동가능한지 여부를 판단 후 이동가능한 경우

현재위치의 숫자+1로 변경 하며 최종위치의 숫자를 구하는 식이다.

 

 

이렇게 그래프 탐색에 대하여 정리를 해보았다.

 

코딩테스트에 자주 나오는 유형 중 하나로 잘 숙지해야 할 것 같다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/DFS%2C%20BFS

CodingTestStudy/FreeDeveloper_Cote