[이것이 코딩테스트다] DFS/BFS

이번 시간에는 알고리즘 문제에서 매우 자주 출제되는 

DFS/BFS에 대해 다뤄보도록 하겠습니다.

그래프의 개념은 단순하지만 문제가 주어졌을 때 

해당 문제가 그래프임을 알아차리는게 전 어려운 것 같습니다ㅜㅜ

해당 내용은 '이것은 코딩테스트다'를 정리한 내용입니다.

---

1. 그래프를 표현하는 방법

   1.1 인접행렬

2차원 배열로 그래프이 연결 관계를 표현하는 방식

# 인접 행렬 방식
INF = 999999999 # 관계가 없는 경우 무수히 큰 값으로 초기화 

graph = [
    [0, 7, 5], # 0과 다른 노드와의 관계
    [7, 0, INF], # 1과 다른 노드와의 관계
    [5, INF, 0] # 2와 다른 노드와의 관계
]

 

   1.2  인접 리스트

리스트로 그래프의 연결 관계를 표현하는 방식

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

# [0]: (0에 연결된 노드,간선)
graph[0].append((1,7))
graph[0].append((2,5))

# [1]: (1에 연결된 노드,간선)
graph[1].append((0,7))

#[2]: (2에 연결된 노드,간선)
graph[2].append((0,5))

print(graph)

---------------------------------------
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

   

2. DFS

깊이 우선 탐색으로 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

-> 재귀함수, 스택를 통해 구현

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.(위의 그래프에서는 1)
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문처리를 한다.(방문 처리는 중복으로 노드를 방문하지 않기 위해 필요!) 방문하지 않은 노드가 없다면 스택에서 최상단 노드를 꺼낸다.

3. 2번 과정을 모든 노드를 방문 할 때까지 반복!

 

최종 방문 순서(숫자가 작은 노드부터!)

1 -> 2 -> 7 -> 6 -> 8 -> 3-> 4 -> 5

 

구현 코드

#DFS

def dfs(graph,v,visited):
    #현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for n in graph[v]:
        if not visited[n]:
            dfs(graph,n,visited)

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

visited = [False] * 9

dfs(graph,1,visited)

1 2 7 6 8 3 4 5

 

3. BFS

가까운 노드부터 탐색하는 알고리즘

-> 큐를 통해 구현

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.(위의 그래프에서는 1)

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

최종 방문 순서(숫자가 작은 노드부터!)

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6 

 

구현 코드

# BFS

from collections import deque

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]:
                queue.append(i)
                visited[i] = True

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

visited = [False] * 9

bfs(graph,1,visited)

1 2 3 8 7 4 5 6

 

4. 음료수 얼려먹기

나의코드 1

# 나의코드
from collections import deque

n,m = map(int, input().split())
data=[]
for c in range(n):
  data.append(list(input()))

# 해당 노드를 방문했는지 확인
visited=[]
for i in range(n):
  visited.append([False]*m)

nx=[1,-1,0,0] # 동 서 남 북
ny=[0,0,1,-1] # 동 서 남 북

# BFS의 시작점 찾기
def find_start():
  for i in range(n): # y축
    for j in range(m): # x축
      if data[i][j] == "0" and visited[i][j]==False :
        start=(i,j) #(y,x)
        return start

result=[]
while True:
  start=find_start()

  if start:
    ice=[]
    queue=deque([start])
    visited[start[0]][start[1]]=True

    while queue:
      v=queue.popleft()
      ice.append(v)
      # v의 4방향을 모두 확인
      for z in range(4):
        dx = v[1] + nx[z]
        dy = v[0] + ny[z]
        if 0<=dx<m and 0<=dy<n:
          # 0이라면 해당 노드를 큐에 추가하고 방문 처리
          if data[dy][dx]=='0' and visited[dy][dx]==False:
            queue.append((dy,dx))
            visited[dy][dx]=True
    result.append(ice)
    
  # 모든 연결된 얼음을 다 찾은 경우  
  else: 
    break

print(len(result))

BFS를 사용하여 큐를 통해 문제를 해결하였습니다. 먼저 data를 받고 해당 노드를 방문하였는지 기록하는 visited 리스트를 생성합니다. 이후 각방향에 대하여 BFS를 사용하여 탐색을 진행하고 '0'이라면 이를 queue에 추가하고 visited를 True로 변경합니다.

하지만 아쉬운 점이 굳이 visited 리스트를 생성할 필요가 있었을까? 방문한 노드를 1로 변경하여 표시할 수 있지 않을까 싶습니다. 그럼 수행시간과 메모리가 훨씬 적게들텐데...

 

나의코드2

불필요한 visited리스트를 제거하고 '1'로 방문한 노드를 표현하였다.

# 나의코드
from collections import deque

n,m = map(int, input().split())
data=[]
for c in range(n):
  data.append(list(input()))

nx=[1,-1,0,0] # 동 서 남 북
ny=[0,0,1,-1] # 동 서 남 북

# BFS의 시작점 찾기
def find_start():
  for i in range(n): # y축
    for j in range(m): # x축
      if data[i][j] == "0":
        start=(i,j) #(y,x)
        return start

result=[]
while True:
  start=find_start()

  if start:
    ice=[]
    queue=deque([start])
    data[start[0]][start[1]]='1'

    while queue:
      v=queue.popleft()
      ice.append(v)
      # v의 4방향을 모두 확인
      for z in range(4):
        dx = v[1] + nx[z]
        dy = v[0] + ny[z]
        if 0<=dx<m and 0<=dy<n:
          # 0이라면 해당 노드를 큐에 추가하고 방문 처리
          if data[dy][dx]=='0':
            queue.append((dy,dx))
            data[dy][dx]='1'
    result.append(ice)

  # 모든 연결된 얼음을 다 찾은 경우  
  else: 
    break

print(len(result))

 

정답코드

# 정답코드
n,m = map(int, input().split())
data=[]
for c in range(n):
  data.append(list(map(int,input())))

# DFS를 통해 특정 노드를 방문한 뒤 연결된 노드 모두 방문
def dfs(x,y):
  # 주어진 범위를 벗어나느 경우에는 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  
  if data[x][y] == 0:
    # 해당 노드 방문처리
    data[x][y] == 1
    # 4방향에 대해 재귀적으로 호출
    dfs(x -1 , y)
    dfs(x , y -1)
    dfs(x + 1, y)
    dfs(x, y + 1)
    return True
  return False

# 모든 노드에 대하여 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS 수행
    if dfs(i, j) == True:
      result +=1

print(result)

 

5. 미로탈출

나의코드(정답코드와 큰 차이가 없음)

# 나의코드
from collections import deque

n,m = map(int, input().split())
data=[]
for c in range(n):
  data.append(list(map(int,input())))


nx=[1,0,-1,0] # 동 남 서 북
ny=[0,1,0,-1] # 동 남 서 북

start=(0,0)

queue=deque([start])

while queue:
  y,x = queue.popleft()
  for z in range(4):
    dx = x + nx[z]
    dy = y + ny[z]
    if 0<=dx<m and 0<=dy<n:
      # 처음 방문한 노드인 경우 최단 거리를 구함
      if data[dy][dx]==1:
        queue.append((dy,dx))
        data[dy][dx] = data[y][x] + 1

print(data[n-1][m-1])

갈 수 있는 길로 표시된 1에 대하여 해당 노드까지 가는 최소한의 경우로를 모두 저장하게 한다. 이를 통해 마지막 칸까지 도달하는 최단길이를 구할 수 있다. 

 

 

 

사진 출처

그래프

https://media.vlpt.us/images/abcd8637/post/8f669d14-0e43-49c2-89b2-07108b60a8d0/스크린샷%202021-01-14%2012.02.31.png