[백준] 1260번 DFS와 BFS 파이썬(Python) 풀이

1260번: DFS와 BFS

[문제]

---

[코드]

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

#인접한
m = [[0] * (n+1) for i in range(n+1)]

#방문
visited = [0] * (n+1)

for i in range(M):
    a, b = map(int, input().split())
    m[a][b] = m[b][a] = 1

#dfs
def dfs(v):
    visited[v] = 1
    print(v, end=' ')

    #재귀 함수 선어 (v와 인접한 곳을 찾고 방문하지 않았다면 시행)
    for i in range(1, n+1):
        if visited[i] == 0 and m[v][i] ==1:
            dfs(i)

def bfs(v):
    #방문해야할 곳을 순서대로 넣을 큐
    queue = [v]


    #dfs를 완료한 visited배열(1로 되어있음)에서 0으로 방문 체크
    visited[v] = 0

    while queue:
        v = queue.pop(0)
        print(v, end=' ')
        for i in range(1, n+1):
            if visited[i] == 1 and m[v][i] == 1:
                queue.append(i)
                visited[i] = 0

dfs(v)
print()
bfs(v)

---

[해설]

bfs와 dfs를 활용하는 기초적인 문제이다.

dfs의 경우에는 쉽게 구현하고 이해 할 수 있었지만 bfs를 이해하려면 약간의 노력이 필요했다. 

자세한 내용은 아래 블로그 참조 💕

파이썬과 컴퓨터 사이언스(고급 알고리즘): 깊이 우선 탐색 (DFS) - 잔재미코딩

DFS와 BFS란?

DFS는 깊이 우선 탐색이며 

BFS는 너비 우선 탐색이다 

아래의 그림을 보면 이해하기가 더 쉽다

 

BFS의경우 A가 시작점이라고 한다면 A와 연결된 B,C를 탐색하고 -> D로가서 G,H,I를 탐색한다

그리고 E로가서 F, J를 탐색하는 방법이다

 

반면 DFS의 경우 A가 시작점이라고 한다면 A와 연결된 B , B와 연결된 D, D와 연결된 E를 탐색하고 다시 D와 연결된 F, 그리고 C로 돌아가 G , H, I를 탐색하고 마지막으로 I와 연결된 J를 탐색한다

 

정리하자면 BFS의경우

A - B - C - D - G - H -I -E F J의 순서로

 

DFS의경우 A - B - D - E - F - C - G - H - I - J 순서이다

 

 

추가적으로 파이썬으로 구현해본 BFS 코드 

from collections import deque

#BFS 함수 정의
def bfs(graph, start, visited):
    #큐 구현을 위해서 deque 라이브러리 이용
    queue = deque([start])
    #현재 노드 망문 저리
    visited[start] = True
    #큐가 빌 때까지 반복
    while queue:
        #큐 에서 한의 원소를 뽑아서  출력

        v = queue.popleft()
        print(queue)
        #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)