[백준_파이썬]1260번_DFS와 BFS

풀이 1

from collections import deque


N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)] # 1부터 시작하니까 인덱스 0버릴 생각
visited = [False] * (N+1) # 인덱스 0은 안쓸 생각


for _ in range(M):
    a, b = map(int, input().split())
    # 연결된 노드들 전부 표시 위함
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

def dfs(graph, v, visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=" ")

    # 해당 노드와 연결되어 있는 노드들이 방문처리 되어 있지 않다면 방문처리
    for i in graph[v]:
        if not visited[i]:
            # 재귀함수를 통해 방문처리
            dfs(graph, i, visited)

def bfs(graph, v, vistied):
    # 큐구현을 위한 deque라이브러리 사용
    queue = deque([v])
    # 현재 노드 방문처리
    visited[v] = True

    # 큐가 빌때까지 반복
    while queue:
        
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=" ")

        # 해당 원소와 연결되고, 아직 방문하지 않은 노드들을 큐에 넣고, 방문처리
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

dfs(graph, V, visited)
print()

visited = [False] * (N+1) # 다시 한 번 초기화
bfs(graph, V, visited)

 

풀이 2.

from collections import deque
queue = deque()

n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split()) # 연결된 두 정점의 정보를 받아야 하므로
    graph[x].append(y)
    graph[y].append(x)

# 숫자가 작은 정점부터 방문하니까 연결된 애들을 정렬해줘야 함
for i in graph:
    i.sort()

def dfs(node):
    # 시작 노드 방문처리
    visited[node] = 1
    # 그때의 노드 출력
    print(node, end=" ")

    # 해당 노드와 연결된 노드면서, 방문하지 않았다면 
    for i in graph[node]:
        if not visited[i]:

            # 재귀 함수를 통해 깊게 방문하기
            dfs(i)

def bfs(node):
    queue.append(node)
    visited[node] = 1

    while queue:
        now = queue.popleft()
        print(now, end=" ")
        # 큐에서 빠져나온 원소와 연결된 노드들 중
        for i in graph[now]:
            if not visited[i]: # 방문하지 않은 노드가 있다면, 방문처리, 큐에넣기
                visited[i] = 1
                queue.append(i)



visited = [0] * (n+1) # 인덱스 0은 안쓸 거니까 정점 +1개 만큼 자리차지
dfs(v)
print()

visited = [0] * (n+1) # 한 번 사용되면 리셋
bfs(v)

 

풀이 2가 더 짧은 시간 소요