[BFS 알고리즘, DFS 알고리즘] DFS와 BFS

기출: BOJ #1260

 

그래프 탐색 대표 문제이다

다음 조건을 만족해야 한다

 

1. 탐색 순서는 낮은 번호의 정점부터 방문한다

2. 두 정점 사이 여러개의 간선이 존재할 수 있다

 

낮은 번호의 정점부터 방문하려면 각 정점과 연결된 정점들을 정렬해줘야 한다

두 정점 사이 여러 개의 간선이 존재할 수 있지만 하나의 간선만을 사용하므로 하나의 간선만 추가시켜준다

 

n,m,v = map(int,input().split())
graph = dict()
bfsAns, dfsAns = list(), list()
bfsVisited, dfsVisited = [False for _ in range(n+1)], [False for _ in range(n+1)]

# 그래프 초기화
for i in range(n+1):
    graph[i] = list()

for _ in range(m):
    x,y = map(int,input().split())
    if y not in graph[x]:
        graph[x].append(y)
        graph[y].append(x)


# 그래프 정렬
for val in graph:
    graph[val].sort()

def BFS(x):
    bfsAns.append(str(x))
    bfsVisited[x] = True
    queue = [x]
    while queue:
        cur = queue.pop(0)
        for next in graph[cur]:
            if bfsVisited[next]: continue
            bfsVisited[next] = True
            queue.append(next)
            bfsAns.append(str(next))

def DFS(x):
    dfsVisited[x] = True
    dfsAns.append(str(x))
    for next in graph[x]:
        if dfsVisited[next]: continue
        DFS(next)

DFS(v)
BFS(v)

print(' '.join(dfsAns))
print(' '.join(bfsAns))