BOJ 1260 DFS&BFS _ 파이썬

📃 문제

백준 1260번 DFS와 BFS

알고리즘 - DFS & BFS

DFS

Depth First Search : 깊이 우선 탐색
시작 노드 부터 가장 깊은 노드까지 깊게 들어감 -> 재귀 호출 이용

visited = [False]* 9
def dfs(graph, v, visited):
    visited(v)=True
    print(v, end='')
    # 현재 노드와 연결된 노드들을 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
     
dfs(graph, 1, visited)

BFS

Breadth First Search : 너비 우선 탐색
시작 노드에 가까운 노드부터 방문 -> 큐 자료구조 이용

간선의 비용이 모두 동일하다면 최단거리 구할 때 사용됨

from collections import deque

def bsf(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[v]:
                queue.append(i)
                visited[i] = True

bfs(graph, 1, visited)

조건

• 정점 번호는 1번부터 N번까지이다.
• 간선은 양방향이다
• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 ... -> 정렬해줘야 한다.

💡 풀이 과정

코드 🥳

import sys
from collections import deque

input = sys.stdin.readline

def dfs(graph, v, visited):
    global dfsorder
    dfsorder.append(v)
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    return

def bfs(graph, startv, visited):
    queue = deque([startv])
    visited[startv] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                bfsorder.append(i)
    return

n, m, startv = map(int, input().split())
dfsorder = []
bfsorder = [startv]

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

for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
for g in graph:
    g.sort()

dfs(graph, startv, visited)
print(' '.join(map(str,dfsorder)))

visited = [False] * (n+1)
bfs(graph, startv, visited)
print(' '.join(map(str, bfsorder)))
# print(*bfsorder)

🔍 정리 & 배운 것

큐 자료 구조

from collections import deque
queue = deque([])

deque 선언 초기값은 list등의 iterable 객체
iterable 객체 : list, dict, set, str, bytes, tuple, range

후입선출 : 가장 예전에 들어왔던 값이 먼저 나간다.
queue.popleft()

list.pop(0)이랑 같은데 큐 자료구조를 사용하는 이유는?

• popleft() : O(1)
• pop(0) : O(N)

* asterisk

파이썬에서 * 의 역할들 중 unpacking 기능을 활용하여 숫자 배열을 풀어 저장할 수 있다.

li = [1,2,3,4,5]
print(*li)
# 1 2 3 4 5
print(*range(1,4))
1 2 3

배열 외에 튜플, 딕셔너리 키 도 가능하다. (참고4)

• 참고
  참고 1 - deque
  참고 2 - iterator
  참고 3 - pop(0)과 시간 복잡도 차이
  참고 4 - asterisk