[Algorithm] 🚩[백준] 1260 (Feat. DFS와 BFS)

BFS(너비 우선 탐색) 알고리즘

> DFS(깊이 우선 탐색) 알고리즘

그래프 전체를 탐색하는 방법 중 특히 "깊이"를 우선적으로 탐색
스택 자료구조(혹은 재귀 함수)를 이용하는 알고리즘이므로 실제 구현할 때 재귀 함수를 활용하면 간결한 코드가 가능하다.
스택은 리스트로 사용할 수 있으며 append와 pop이 O(1)이다.

• 주로 경우의 수를 알고 싶을 때 사용

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리
2. 스택 내 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드를 스택에 삽입 후 방문처리, 만약 인접 노드가 모두 방문 처리되면 스택 내 최상단 노드 꺼냄
3. 2번 과정 끝까지 반복

> BFS(너비 우선 탐색) 알고리즘

그래프에서 가까운 노드부터 우선적으로 탐색

• 큐 자료구조를 이용하며 특정 조건에서의 최단 거리를 구할 때 사용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 2번 과정 끝까지 반복

---

BFS와 DFS가 헷갈려서 비교해보았다.

- BFS : 정점과 같은 레벨에 있는 노드들을 먼저 탐색

- DFS : 정점의 자식들을 먼저 탐색

< BFS >

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited=[False]*9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

< DFS >

# 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)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited=[False]*9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

---

> 문제풀이

DFS와 BFS는 트리나 그래프 구조를 가지고 있어야 서로 연결된 노드를 파악할 수 있다.

📌 하지만 이 문제에서는 인접 행렬 방식으로 행과 열을 통해서 값을 해당 숫자들이 연결되어 있는지 확인하는 방법으로 풀어야 한다.
인덱스와 값을 일치시키기 위해 (n+1) * (n+1)의 행렬을 리스트로 만들고 0을 채운다.
연결된 숫자들 값을 m개 입력 받아서 해당 행과 열을 연결시켜야 하므로 1로 바꾼다.
즉, 행의 숫자와 열의 숫자가 연결되어 있음을 표시하는 것이다.

from collections import deque

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

graph = [[0] * (n+1) for _ in range(n+1)]

for _ in range(m):
    m1, m2 = map(int, input().split())
    # 노드 연결하기
    graph[m1][m2] = graph[m2][m1] = 1

## 너비 우선 탐색 (BFS)
def bfs(start_v):
    visited = [start_v]
    # 리스트를 써서 pop(0)하면 시간 복잡도 O(N)
    # deque를 써서 popleft()하면 시간 복잡도 O(1)
    queue = deque()
    queue.append(start_v)

    while queue:
        v = queue.popleft()
        print(v, end=' ')

        for w in range(len(graph[start_v])):
            if graph[v][w] == 1 and (w not in visited):
                visited.append(w)
                queue.append(w)


## 깊이 우선 탐색 (DFS)
def dfs(start_v, visited=[]):
    visited.append(start_v)
    print(start_v, end=' ')

    for w in range(len(graph[start_v])):
        if graph[start_v][w] == 1 and (w not in visited):
            dfs(w, visited)

dfs(v)
print()
bfs(v)