[백준] 1260 DFS와 BFS(Python)

1. 생각 정리

• 처음에 간선 정보 입력을 2차원 리스트에 [[1,2], [1,3]]이런 식으로 담으려 했는데 문제를 더 간단히 풀기 위해서는 빈 2차원 리스트를 생성한 뒤 1행에 1과 연결된 정점 넣어주기, 2행에 2와 연결된 정점 넣어주기... 의 느낌으로 입력받는 게 더 편함
• visited 리스트를 따로 만들어서 이미 탐색된 정점에 대한 정보를 관리
• DFS의 경우에는 재귀함수로, BFS의 경우에는 deque를 이용하여 구현

2. 코드 구현

from collections import deque
#정점 개수 N, 간선 개수 M, 탐색 시작 정점번호 V
N, M, V = map(int, input().split())
mapp = [[] for _ in range(N+1)]
#두개의 정점이 연결되어있다는 간선정보 
for _ in range(M):
    x, y = map(int, input().split())
    mapp[x].append(y)
    mapp[y].append(x)
 
for i in mapp:
    i.sort()
 
def dfs(V):
    print(V, end=' ')
    visited[V] = True
    
    for i in mapp[V]:
        if visited[i] == False:
            dfs(i)
def bfs(V):
    q = deque([V])
    while q:
        temp = q.popleft()
        if not visited[temp]:
            visited[temp] = True
            print(temp, end=' ')
            for i in mapp[temp]:
                if not visited[i]:
                    q.append(i)
 
visited = [False]*(N+1)
dfs(V)
print()
visited = [False]*(N+1)
bfs(V)