chapter 5. DFS/BFS

DFS	- 재귀호출 - 백트래킹 - 조건 많은 그래프
BFS	- 큐 - 최단 거리, 최소 비용 문제 - 모든 간선의 비용 1

DFS/BFS 둘 다 visited 배열 만들어서 방문처리를 해줘야 한다

반복문이 재귀함수보다 빠르게 동작하는 경우가 많기 때문에 DFS, BFS 둘 다로 구현 가능하면 BFS를 사용하는 게 낫다

 

1. 스택

선입후출 구조로 한쪽에서만 입력과 출력이 일어나기 때문에박스 쌓기에 비유된다

stack=[]
stack.append(5) #5
stack.append(2) #5 2
stack.append(3) #5 2 3
stack.append(7) #5 2 3 7
stack.pop() #5 2 3
stack.append(1) #5 2 3 1
stack.append(4) #5 2 3 1 4
stack.pop() #5 2 3 1
 
print(stack[::-1]) #1 3 2 5

 

 

2. 큐

선입선출 구조로 한쪽에서는 입력이, 한쪽에서는 출력이 일어나게 된다. 대기줄에 비유된다.

from collections import deque
 
queue=deque()
 
queue.append(5) # 5
queue.append(2) # 5 2
queue.append(3) # 5 2 3
queue.append(7) # 5 2 3 7
queue.popleft() # 2 3 7
queue.append(1) # 2 3 7 1
queue.append(4) # 2 3 7 1 4
queue.popleft() # 3 7 1 4
 
print(queue) # deque([3, 7, 1, 4])
queue.reverse() #
print(queue) # deque([4, 1, 7, 3])
 
print(list(queue)) # [4, 1, 7, 3]

 

4. DFS

Depth-First Search, 깊이 우선 탐색이다

 

 

그래프는 2가지 방식으로 표현할 수 있다

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현
• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현

 

 

 

① 인접 행렬 방식

INF=999999999 #무한
 
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]
 
print(graph) # [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

자기자신은 0으로 서로 연결 돼 있지 않은 노드끼리는 INF(무한, infinity)로 초기화한다

 

 

 

② 인접 리스트 방식

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))
 
print(graph) # [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

인접 리스트 방식은 인접 행렬 방식에 비해 두 노드가 연결돼 있는지 정보를 얻는 속도가 느리다.

 

 

DFS는 깊이 우선으로 번호가 낮은 순서부터 처리한다, 재귀호출한다

 

def dfs(graph, v, visited):
    #현재 노드 방문 처리
    visited[v]=True
    print(v, end=' ')
 
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if visited[i]==False:
            dfs(graph, i, visited)
 
graph=[[], #0번 노드 없음
       [2, 3, 8],
       [1, 7],
       [1, 4, 5],
       [3, 5],
       [4, 3],
       [7],
       [2, 6, 8],
       [1, 7]]
 
visited=[False]*9
 
dfs(graph, 1, visited) #1 2 7 6 8 3 4 5

 

 

5. BFS

Breadth-Frist-Search 너비우선 탐색이다

가장 가까운 노드부터 탐색한다. 큐를 사용한다

 

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 visited[i]==False:
                queue.append(i)
                visited[i]=True
 
graph=[[], #0번 노드 없음
       [2, 3, 8],
       [1, 7],
       [1, 4, 5],
       [3, 5],
       [4, 3],
       [7],
       [2, 6, 8],
       [1, 7]]
 
visited=[False]*9
 
bfs(graph, 1, visited) #1 2 3 8 7 4 5 6 
 

 

코딩테스트에서 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각해보자

 

 

 

① 음료수 얼려 먹기

import sys
input=sys.stdin.readline
 
n,m = map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))
 
def dfs(a, b):
    #종료 조건 지정 잘 해주기
    # 범위 넘어가면 종료
    if a<0 or a>n-1 or b<0 or b>m-1:
        return False
    # 칸막이거나 방문했으면 종료
    if graph[a][b]==1:
        return False
 
    graph[a][b]=1
 
    dfs(a, b+1) #동
    dfs(a, b-1) #서
    dfs(a+1, b) #남
    dfs(a-1, b) #북
 
    return True
 
 
result=0
for i in range(n):
    for j in range(m):
        if dfs(i, j):
            result+=1
 
print(result)

처음에 띄어쓰기 없이 입력했는데 어떻게 배열로 입력됐는지 궁금했는데 문자열 형식이 iterable한 형식이라 

map을 이용해 문자 하나하나 int로 변경하는게 가능한 거였다.

재귀호출은 좀 더 공부해야 적용 가능할 듯 하다

 

 

② 미로 탈출

import sys
from collections import deque
input=sys.stdin.readline
 
# 행, 열
n, m=map(int, input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))
 
# 0무조건 피하고, 최대한 오른쪽으로, 최대한 아래로
def bfs(a, b):
    queue=deque()
    queue.append((a, b))
    #동서남북
    dc=[0, 0, 1, -1]
    dd=[1, -1, 0, 0]
 
    while queue:
        c, d=queue.popleft()
 
        for i in range(4):
            #탐색하고자 하는 인덱스
            nc, nd=c+dc[i], d+dd[i]
 
            if nc>n-1 or nc<0 or nd>m-1 or nd<0:
                continue
 
            if graph[nc][nd]==1:
                graph[nc][nd]=graph[c][d]+1
                queue.append((nc, nd))
 
    # 도착
    return graph[-1][-1]
 
 
# bfs 호출
print(bfs(0, 0))
print(graph)

 

입력 예시	출력 예시
5 6 101010 111111 000001 111111 111111	10

 

 

 

 

출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)