1260번: DFS와 BFS (acmicpc.net)

##
# 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
두 방식으로 그래프를 순회하도록 하면 된다.


##
import sys
from collections import deque
input = sys.stdin.readlines

l = list(map(lambda x:x.rstrip().replace('\x1a',''),input()))
N,M,V = map(int,l[0].split())
l2 = list(map(lambda x:x.split(),l[1:]))

graph = [[] for i in range(N+1)]
# 인접 리스트 방식으로 표현
for a,b in l2:
    graph[int(a)].append(int(b))
    graph[int(b)].append(int(a))
# 정렬
for edgs in graph:
    edgs.sort()

visited_DFS = [False for i in range(N+1)]
visited_BFS = [False for i in range(N+1)]

dfs_print = []
bfs_print = []

def DFS(graph,V):
    visited_DFS[V] = True
    #print(V,end=' ')
    dfs_print.append(V)
    for i in graph[V]:
        if visited_DFS[i] == False:
            DFS(graph,i)
    return None

def BFS(graph,V):
    q = deque([V])
    visited_BFS[V] = True

    while (len(q) != 0):
        tmp = q.popleft()
        #print(tmp,end=' ')
        bfs_print.append(tmp)

        for i in graph[tmp]:
            if visited_BFS[i] == False:
                q.append(i)
                visited_BFS[i] = True
    return None

DFS(graph,V)
print(' '.join(list(map(str,dfs_print))))
BFS(graph,V)
print(' '.join(list(map(str,bfs_print))))
생각보다 엄청 오래 걸렸는데, 그래프 문제를 거의 풀어본적이 없기도 하고
입력에서 주어지는 간선이 양방향임을 놓쳐서 한 방향만 삽입해서 예제 2번은 결과가 틀리게 나오기도 했다.

인접 리스트 방식으로 표현한다는 것을 처음 알았는데
대부분 그래프가 1번부터 N번까지 쓰고 있으므로 0번은 [], 이렇게 비워두고 나머지 공간을 이용해서 그래프를 표현하고 순회하는 과정을 구현하면 된다.