백준 1260 DFS와 BFS (Python)

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

1260번: DFS와 BFS

단순한 그래프 문제이다.

 

입력받은 edge를 배열에 저장하고 해당 배열을 DFS, BFS에 맞게 탐색하면서 풀었다.

 

DFS, BFS에서의 다른 점은 BFS는 바로바로 다음 방문 배열에 넣은 반면, DFS는 해당 노드에서 인접한 노드를 모두 구해 배열로 만든 후 다음 방문 배열 앞으로 넣어주었다.

 

import sys

N, M, V = map(int, sys.stdin.readline().split())

graph = [[False for _ in range(N+1)] for _ in range(N+1)]

for i in range(M):
    V1, V2 = map(int, sys.stdin.readline().split())
    graph[V1-1][V2-1] = True
    graph[V2-1][V1-1] = True

DFS, BFS = [False for i in range(N)], [False for i in range(N)]
to_visit = [V-1]

while to_visit:
    cur_node = to_visit.pop(0)
    if DFS[cur_node]:
        continue
    save_to_visit = []
    for i in range(N):
        if graph[cur_node][i] and not DFS[i]:
            save_to_visit.append(i)

    to_visit = save_to_visit + to_visit

    print(cur_node + 1, end=' ')
    DFS[cur_node] = True

print()

to_visit = [V-1]

while to_visit:
    cur_node = to_visit.pop(0)
    if BFS[cur_node]:
        continue

    for i in range(N):
        if graph[cur_node][i] and not BFS[i]:
            to_visit.append(i)

    print(cur_node + 1, end=' ')
    BFS[cur_node] = True