[백준] DFS와 BFS_1260번

[백준] DFS와 BFS

---

문제

링크 : BOJ

---

---

풀이

DFS와 BFS의 이해에 대한 문제이다.
이전에 C++로 풀었는데 파이썬으로 다시 푼 결과이다.

먼저, 탐색을 시작하기 전에 순서대로 탐색하기 위해 2차원 배열에 담긴 수를 정렬해야 한다.
그리고 탐색을 시작하는 데 dfs는 재귀 함수를 이용해서 풀어준다. 반면에 bfs에서는 deque라이브러리를 이용해서 푼다.
deque(데크)는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다.
list와 비슷하게 append(), pop() 등의 메소드를 이용할 수 있다. 출처EXCELSIOR

선입선출을 이용하기 위해 append()와 popleft()를 이용한다.

from collections import deque
#dfs
def dfs(data, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in data[v]:
        if not visited[i]:
            dfs(data, i, visited)

#bfs
def bfs(data, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in data[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m, v = map(int, input().split())
data = []
for _ in range(n+1):
    data.append([])
for _ in range(m):
    x, y = map(int, input().split())
    data[x].append(y)
    data[y].append(x)
for i in range(n+1):
    data[i] = sorted(data[i])

visited = [False] * (n+1)

dfs(data, v, visited)
print()
visited = [False] * (n+1)
bfs(data, v, visited)

---

실수했던 점

---