본문 바로가기

Algorithm

[백준] DFS와 BFS 1260 Python

본 블로그 DataStructure 카테고리에 있는 소스코드를 활용하면 된다. 하지만 이 문제의 경우 인접리스트를 오름차순으로 정렬된 상태에서 DFS와 BFS를 수행하므로 각 역할 수행 시 인접리스트를 정렬하고 수행한다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
queue = []
lists = []
visited = []
 
def dfs(x):
    print(x, end=" ")
    lists[x].sort()
    for i in lists[x]:
        if i not in visited:
            dfs(i)
 
def bfs(x):
    while len(queue)!=0:
        current = queue.pop(0)
        lists[current].sort()
        print(current, end = " ")
        for i in lists[current]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
 
 
n, e, x= map(int, input().strip().split())
 
for i in range(n+1):
 
for i in range(e):
    a,b = map(int, input().strip().split())
    lists[a].append(b)
    lists[b].append(a)
 
dfs(x)
print("")
bfs(x)