[백준] 1260. DFS와 BFS - Python

[Silver II]

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

풀이

2차원 배열을 통해 네트워크(그래프)를 생성하고, BFS와 DFS를 각각 돌려 결과를 출력한다.

정점 번호가 작은 것 먼저 방문해야 하므로, 그래프를 돌면서 각 정점들을 정렬한 후 DFS와 BFS를 실행한다.

DFS이후 visited 리스트를 초기화해야 BFS도 동일하게 실행할 수 있기 때문에 DFS 이후 initVar()를 통해

리스트를 초기화하여 BFS를 실행한다.

from collections import deque

global graph
global visited

def initVar():
    for i in range(n + 1):
        visited[i] = False

def dfs(cur):
    if visited[cur]:
        return
    visited[cur] = True
    print(cur, end=" ")
    for i in range(len(graph[cur])):
        dfs(graph[cur][i])

def bfs(cur):
    queue = deque()
    queue.append(cur)
    visited[cur] = True

    while queue:
        cur = queue.popleft()
        print(cur, end=" ")
        for i in range(len(graph[cur])):
            if not visited[graph[cur][i]]:
                queue.append(graph[cur][i])
                visited[graph[cur][i]] = True

# main
n, m, v = map(int, input().split())

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

for i in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for i in range(len(graph)):
    graph[i].sort()

dfs(v)
initVar()
print()
bfs(v)