[8/27] 1260 (DFS와 BFS)

실버2 문제

내 코드

from collections import deque

n, m, v = map(int, input().split())
arr = [[] for i in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    if (a > b):
        a, b = b, a
    arr[a].append(b)
    arr[b].append(a)

for i in range(len(arr)):
    arr[i].sort()
    
# 깊이 우선 탐색 (스택)
def dfs(array, visited, v):
    
    visited[v] = True
    print(v, end=" ")
    for i in array[v]:
        if (visited[i] == False):
            dfs(array, visited, i)
    
visited = [False] * (n+1)
dfs(arr, visited, v)
print()

# 너비 우선 탐색 (큐)
def bfs(array, visited, v):
    queue = deque([v])
    
    while queue:
        new = queue.popleft()
        if (visited[new] == False):
            visited[new] = True
            print(new, end=" ")
            for i in array[new]:
                queue.append(i)
                
visited = [False] * (n+1)
bfs(arr, visited, v)

로직

• 정석대로 풀었다.

효율적인 코드

그래프 입력 방법을 바꿔야할 것 같다.