DFS 와 BFS 개념

 

* <이것이 취업을 위한 코딩테스트다 with 파이썬> 책과 강의를 참고하여 작성하였습니다.

 

DFS: Depth-First-Search 깊이우선탐색

- 멀리 있는 노드를 우선으로 탐색. 스택 자료구조 사용하나, 스택말고 재귀함수로 더 쉽게 나타낼 수 있다.

- 인접 노드 중 미방문 노드를 하나씩 스택에 쌓고 방문처리. (보통 문제의 조건은 번호가 낮은 순서대로) 

- 인접 노드 중 미방문 노드가 없는 경우 해당 노드를 스택에서 꺼낸다.

- 데이터 개수가 N개인 경우 O(N) 소요

BFS: Breadth-First-Search 너비우선탐색

- 가까운 노드를 우선으로 탐색. 큐 자료구조 (선입선출) 를 사용한다. w/ deque 라이브러리

- 인접 노드 중 미방문 노드를 전부 큐에 넣고 방문처리.

- O(N) 시간 소요.

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)
bfs(graph,1,visited)

DFS:

def dfs(graph, v, visited):
  visited[v]=True  # 방문처리.
  print(v,end=' ')
  for i in graph[v]:
    if not visited[i]:  # 인접 노드 중 미방문 노드만 방문.
      dfs(graph, i, visited)

BFS:

from collections import deque
def bfs(graph, start, visited):
  queue = deque([start]) # start를 원소로 가진 deque 생성.
  visited[start] = True
  while queue:  # 큐가 빌 때까지 반복
    v = queue.popleft() # 방문한 노드는 하나씩 큐에서 제거.
    print(v,end=' ')
    for i in graph[v]:  # 방금 제거한 노드의 미방문 인접 노드 큐에 추가하여 방문처리.
      if not visited[i]:
        queue.appends(i)  
        visited[i]=True

---

 

 

p.149 음료수 얼려 먹기

dfs bfs 를 이해하긴 했으나 문제에 응용하지는 못했다.. 사실 아예 손도 못댐.

문제에 쓰질 못하면 완전히 이해한게 아니겠지..

우선 이코테 답안을 그대로 써보았다:

from collections import deque

n,m=map(int,input().split())

graph=[]
for i in range(n):
  graph.append(list(map(int,input())))

def dfs(x,y):
  if x<=-1 or x>=n or y<=-1 or y>=m:
    return False
  if graph[x][y]==0:
    graph[x][y] = 1
    #상하좌우의 노드 각각에 대해 방문처리
    dfs(x-1,y) #top
    dfs(x,y-1) #left
    dfs(x+1,y) #bottom
    dfs(x,y+1) #right
    return True
  return False

result=0
for i in range(n):
  for j in range(m):
    if dfs(i,j) == True:
      result += 1
print(result)

 

앞의 예제에서와 공통된 DFS 틀은 

1) 현재 노드를 방문처리. (미방문인 경우)

2) 그 다음 미방문 인접 노드들을 방문처리. by 재귀함수.

식으로 짜여진다.

 

그리고, DFS 를 쓰든 BFS 를 쓰든, 우선 주어진 그래프를 어떻게든 리스트의 형태로 정리해야 한다.

 

또 앞의 예제에선 visited라는 리스트를 따로 만들어 방문 여부의 기록을 했지만, 

이 문제에서처럼 0과 1로 방문과 미방문을 이미 구분짓고 있다면 visited같은 리스트를 굳이 또 만들 필요가 없다.

 

---

 

p.152 미로 탈출

 

내 답안 (오답, 미완) :

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

from collections import deque

def bfs(x,y):
  count=0
  que=deque((x,y))
  while que:
    v=que.popleft()
    count+=1
    if graph[v[0]+1][v[1]]==1:
      que.append(graph[v[0]+1][v[1]])
    if graph[v[0]][v[1]+1]==1:
      que.append(graph[v[0]][v[1]+1])
    .........미완

 

풀이를 참고하여 작성한 답안:

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

from collections import deque
def bfs(x,y):
  # 상,하,좌,우 순서의 방향벡터:
  dx=[-1,1,0,0]  ### 방향벡터는 함수 밖에 있어도 된다.... (아니 밖에 있어야 하나?)
  dy=[0,0,-1,1]
  que=deque()
  que.append((x,y))
  while que:
    x,y = que.popleft() # 방문처리 한 현재 노드를 큐에서 제거 & 현재 위치를 임시로 저장.
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or ny<0 or nx>=n or ny>=m: # 그래프 벗어난 경우
        continue
      if graph[nx][ny]==0: # 벽인 경우
        continue
      if graph[nx][ny]==1: ### 미방문 노드만!!
        graph[nx][ny] = graph[x][y]+1 ###
        que.append((nx,ny)) # 미방문 인접 노드를 큐에 추가.
  return graph[n-1][m-1]

print(bfs(0,0))

풀이를 읽어볼 때는 얼추 이해가 되면서도

bfs는 아직 혼자서는 한 번에 성공시키기 어렵다.. 

이 문제는 방향벡터까지 쓴다,,

풀이에서 처음에 이해 안됐던 건 어차피 최단 거리를 찾는 거면 굳이 왜 상, 좌 방향까지 따져보는걸지,, 

근데 그냥 단순히 미로가 꼭 우하향으로 나있는 건 아니니까 얼마든지 위로 혹은 좌로 갔다가 다시 내려와야 할 수도 있는 것이었다.... (이것도 방금 깨달았다)

 

어쨌든, BFS 의 틀은 

1) 가장 처음에 방문했던 (큐의 가장 왼쪽에 있는) 노드를 큐에서 제거한다.

2) 방금 제거했던 노드의 인접 노드 중 미방문 노드들을 큐에 모두 추가한다.

이 두 과정을 큐가 텅 빌 때까지 계속 반복하는 것이다. 

 

요약하자면,

DFS는 재귀함수를 통해 인접 노드들을 방문처리하는 식이라면,

BFS는 while 반복문을 통해 인접 노드들을 방문처리하고 (큐에 추가하고) 하나씩 큐에서 제거하는 식이다.

둘 다 탐색이 끝날 때까지 노드들을 차례대로 방문하는 작업을 '반복'해야 하는데

DFS는 재귀함수로, BFS는 while문으로 반복하는 것이다. 

 

DFS - 후입선출 - 스택 자료구조 - 깊이 우선 탐색 

BFS - 선입선출 - 큐 자료구조 - 너비 우선 탐색