[백준] 1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

어떻게 풀면 좋을까?

방문했는지 여부를 저장하는 배열을 만든다. 방문을 하지 않은 곳 만 방문하게 해서 구하면 된다.

풀이

from collections import deque
n, m, v = map(int, input().split())

# 1번부터 시작
graph = [[] for i in range(n + 1)]
check_visit = [False] * (n + 1)

# 그래프에 입력값을 넣어준다. 양방향인거 고려해서!
# [[], [1, 2, 3], [1, 4], [1, 4], [2, 3, 4]]
for i in range(m):
    a, b = map(int, input().split())        
    graph[a].append(b)
    graph[b].append(a)
# 작은거부터 들르기
for i in range(len(graph)):
    graph[i].sort()

dfs_result = []

def dfs(start):
    dfs_result.append(start)
    # start 지점에 방문했다!    
    check_visit[start] = True
    for i in graph[start]:
        if check_visit[i] == False:
            dfs(i)
            check_visit[i] = True
dfs(v)

check_visit = [False] * (n + 1)

bfs_result = []

def bfs(start):
    # start 지점에 방문했다!
    check_visit[start] = True
    deq = deque([start])
    while(deq):
        cur = deq.popleft()
        bfs_result.append(cur)
        for i in graph[cur]:
            if check_visit[i] == False:
                deq.append(i)
                check_visit[i] = True
bfs(v)

for i in range(len(dfs_result)):
    print(dfs_result[i], end=" ")
print()
for i in range(len(bfs_result)):
    print(bfs_result[i], end=" ")