[알고리즘] 개념 - BFS/DFS

1. visited / 이중반복문 풀이 차이

이중반복문 - 2차원배열, 좌표, 정점 별 특징

visited - 단순 정점, 간선 정보

	visited	이중반복문
문제 차이	단순 정점, 간선 정보	2차원배열, 좌표, 정점 별 특징
배열 선언	arr=[ []*(n+1) for _ in range(n+1) ]	arr=[]
배열 삽입	arr[a].append(b)	arr.append()
백준	1260, 2606, 11724	4963, 2667

# visited
arr=[ []*(n+1) for _ in range(n+1) ]
arr[a].append(b)

# 이중 반복문
arr=[]
arr.append()

• visited 이용한 대표코드 (1260)

  import sys
  input=sys.stdin.readline
  from collections import deque
  
  n,m,v=map(int, input().split())
  arr=[[]*(n+1) for i in range(n+1)]
  visited_bfs=[False]*(n+1)
  visited_dfs=[False]*(n+1)
  
  for i in range(m):
      a,b=map(int, input().split())
      arr[a].append(b)
      arr[b].append(a)
  
  def bfs(v):
      queue=deque([v])
      visited_bfs[v]=True
      while queue:
          k=queue.popleft()
          print(k, end=" ")
          for i in sorted(arr[k]):
              if visited_bfs[i]==False:
                  queue.append(i)
                  visited_bfs[i]=True
  
  def dfs(v):
      visited_dfs[v]=True
      print(v, end=" ")
      for i in sorted(arr[v]):
          if visited_dfs[i]==False:
              dfs(i)
  
  dfs(v)
  print()
  bfs(v)

• 2차원배열 이용한 대표코드 (2178)

  import sys
  input=sys.stdin.readline
  from collections import deque
  
  n,m=map(int, input().split())
  arr=[]
  
  dx, dy= [-1, 1, 0, 0], [0, 0, -1, 1]
  for i in range(n):
      arr.append(list(map(int, input().rstrip())))
  
  def bfs(i, j):
      queue=deque()
      queue.append((i, j))
      while queue:
          x,y = queue.popleft()
          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 arr[nx][ny]==1:
                  arr[nx][ny]=arr[x][y]+1
                  queue.append((nx, ny))
      return arr[n-1][m-1]
  
  print(bfs(0,0))

---

ref1 , ref2 , ref3

2. BFS/DFS 판단 기준

BFS - 최단거리, 최소횟수

DFS - 모든 경우 탐색, 이동시에 가중치/제약

	BFS	DFS
	최단거리, 최소횟수	모든 경우 탐색, 이동시에 가중치/제약
특징	항상 최단 경로를 보장	최단거리 보단 모든 경우 탐색
방문	연결된 가까운 노드	연결된 브랜치 모두 방문
문제	2178

bfs(너비우선) : 최단거리, 또는 최소횟수

• 특징
  • 현재 정점에 연결된 가까운 점들부터 탐색(현재 나의 위치에서 가장 가까운 노드들을 모두 방문)
  • 방문하면서 현재위치 pop, 방문할 곳 append, 방문한 곳 check
• 유리한 경우
  • 미로탐색 중 최단 거리/최단 횟수 구하는 경우, 임의의 경로를 찾는 문제
    • 항상 최단 경로를 보장 → Optimal한 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최단 거리
    • 탐색의 횟수를 구해야 하는 경우(7576번 토마토 문제)

dfs(깊이우선) : 모든 경우

• 특징
  • 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 (현재 나의 위치에서 연결된 브랜치를 모두 방문 후 다음 브랜치로 넘어가는 방법)
    • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법
    • 모든 깊이를 탐색하고 성공 유무를 결정하기 때문에 최단거리 문제에는 어울리지 않음
    • 일반적으로 모든 경우를 다 탐색해야 하는 경우는 DFS가 더 선호
• 유리한 경우
  • 모든 노드를 방문하고자 할 때 이 방법을 선택
    미로*탐색 진행 시 이동할 때 마다 가중치가 붙거나 이동 과정에서 제약이 있을 경우
    • 모든 경우 탐색 - 재귀적인 특징과 백트래킹을 이용하여 모든 경우를 하나씩 전부 탐색하는 경우
    • Optimal한 답을 찾는 것이 아닌 경우
  • Graph의 크기가 클 경우
  • 경로의 특징을 저장해야 하는 경우 ex) 경로의 가중치, 이동 과정에서의 제약

• 둘 다 가능
  • 2606, 2667, 11724