문제 링크

문제 해결

별다른 조건이 없는 DFS, BFS 문제

입력으로 주어지는 정점은 key로 하고 각 간선들을 담는 리스트를 value로 하여 dictionary 자료형으로 구현하였다.

정석적인 방법으로 DFS는 초기 정점으로 시작하여 정점이 가지고있는 간선들을 순회하면서 재귀호출로 풀고, BFS는 간선들을 순회하면서 queue에 추가하는 방식으로 풀이하였다.

처음에 양방향의 조건을 못보고 단방향 그래프로 구현했다가 테케2번이 꼬여서 잠깐 헤맸다.
이전에 c++로 풀었던 풀이가 있어서 봤는데, 그래프를 key,value형태가 아닌 2차원 배열로 저장하여 풀었었다. 이 방법도 나중에 다시 파이썬 이중리스트로 구현해서 속도를 비교해봐야겠다.

코드

from collections import deque 

def DFS(vertex):
    dfs_result.append(vertex)

    for edge in graph[vertex]:
        if visited_dfs[edge] == True: 
           continue
        if len(graph[edge]) == 0:
           continue
        visited_dfs[edge] = True
        DFS(edge)

    return

def BFS(start):
    dq = deque()
    dq.append(start)

    while(len(dq)):
        vertex = dq.popleft()
        bfs_result.append(vertex)

        for edge in graph[vertex]:
            if visited_bfs[edge] == True: 
               continue
            if len(graph[edge]) == 0:
               continue
            visited_bfs[edge] = True
            dq.append(edge)

    return

#-------------------------------------------------------------------------------

# n: 정점의 갯수
# m: 간선의 갯수
# v: 시작 정점
n,m,v = map(int,input().split())

# 그래프 초기화
graph = {}
visited_dfs = {}
visited_bfs = {}
for index in range(1, n+1):
    graph.setdefault(index, [])
    visited_dfs.setdefault(index, False)
    visited_bfs.setdefault(index, False)

for _ in range(m):
    v1,v2 = map(int, input().split())
    # 양방향 간선 삽입
    graph[v1].append(v2)
    graph[v2].append(v1)

# 동일 간선 오름차순 정렬
for key in graph.keys():
    graph[key].sort()

dfs_result = []
bfs_result = []

# 첫번째 정점부터 시작
visited_dfs[v] = True
visited_bfs[v] = True
DFS(v)
BFS(v)

for v in dfs_result:
   print(v, end=" ")
print("")
for v in bfs_result:
   print(v, end=" ")