[알고리즘] DFS, BFS + 문제풀이

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

인접 리스트 : 리스트로 그래프의 연결 관계 표현

 

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)

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

• 가까운 노드부터 탐색하는 알고리즘
• DFS에 비해 실제 수행시간이 더 좋은 편
• 큐 이

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	백준 1260번	실버3	△	20230207
2	백준 2178번	실버1	△	20230207
3	백준 2606번	실버3	O	20230208
4	프로그래머스	Level2	O	20230210
5	백준 7576번	골드5	O	20230213
6	백준 7569번	골드5	O	20230213