백준 / DFS와 BFS / 1260번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: DFS와 BFS / 1260번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/1260

 

문제 설명

 

---

 

나의 풀이

 

from collections import deque

def bfs(graph, visit, start):
    q = deque([start])
    visit[start] = True

    while q:
        x = q.popleft()
        print(x, end = " ")
        for i in graph[x]:
            if not visit[i]:
                q.append(i)
                visit[i] = True

def dfs(graph, visit, start):
    visit[start] = True
    print(start, end = " ")

    for i in graph[start]:
        if not visit[i]:
            dfs(graph, visit, i)

point, weight, st = map(int, input().split())

graph_to = [[] for _ in range(point + 1)]
visited_dfs = [False] * (point + 1)
visited_bfs = [False] * (point + 1)

for _ in range(weight):
    x, y = map(int, input().split())
    graph_to[x].append(y)
    graph_to[y].append(x)

for i in range(1, point + 1):
    graph_to[i].sort()

dfs(graph_to, visited_dfs, st)
print()
bfs(graph_to, visited_bfs, st)

---

※ 알아야 할 것

DFS와 BFS의 구조를 알아야 풀 수 있다.

 

https://newkimjiwon.tistory.com/81

깊이 우선 탐색(DFS, Depth-First Search)

https://newkimjiwon.tistory.com/77

너비 우선 탐색(BFS, Breadth-First Search)