[Python 3] BOJ - 1260 "DFS와 BFS"

# 문제 링크 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 # 풀이 :

 사용해야 하는 알고리즘이 정해저 있으므로, 문제의 조건 중 방문하는 정점이 여러개이면 정점 번호가 작은 것 부터 방문한다는 조건만 만족시키면 되므로 인접리스트를 최소 힙으로 구현하면 된다. 따라서 인접리스트를 계속 pop하면서 방문한 정점인지 아닌지만 체크하면 된다.

 

 # 코드

import sys, heapq, collections

# 입력 및, dfs/bfs 인접리스트 각각 생성
n,m,v = map(int, sys.stdin.readline().split())
adj_dfs = [[] for _ in range(n)]
adj_bfs = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    # 넣을 때 최소 힙 우선순위 기준으로 넣는다
    heapq.heappush(adj_dfs[a - 1], b - 1)
    heapq.heappush(adj_dfs[b - 1], a - 1)
    heapq.heappush(adj_bfs[a - 1], b - 1)
    heapq.heappush(adj_bfs[b - 1], a - 1)

check = [False] * n

# dfs : path에 dfs 방문 경로를 넣어주는 함수
def dfs(start, path):
    check[start] = True
    path.append(start + 1)
    while adj_dfs[start]:
        # 최소 힙으로 next를 자동으로 뽑음
        next = heapq.heappop(adj_dfs[start])
        if check[next] == False:
            check[next] = True
            dfs(next, path)

# init : 전역 배열 check를 dfs와 bfs가 공유하고 있으므로 초기화해주는 함수
def init(c):
    for i in range(n):
        c[i] = False

# bfs : path에 bfs 방문 경로를 넣어주는 함수
def bfs(start, path):
    q = collections.deque()
    q.append(start)
    check[start] = True
    while q:
        now = q.popleft()
        path.append(now + 1)
        while adj_bfs[now]:
            next = heapq.heappop(adj_bfs[now])
            if check[next] == False:
                check[next] = True
                q.append(next)

dfs_ans = []
bfs_ans = []

dfs(v - 1, dfs_ans)
init(check)
bfs(v - 1, bfs_ans)

# 정답 출력
print(' '.join(map(str, dfs_ans)))
print(' '.join(map(str, bfs_ans)))