[BOJ 1260] DFS와 BFS

DFS & BFS

[BOJ 1260] DFS와 BFS

문제

구조화

• 단순한 DFS, BFS 구현
• node 탐색 순서 출력
• 방문 여부가 변경될 때 해당 노드를 ans에 추가하여 최종 결과 Return
• 주의 : edge의 입력이 오름차 순이 아니므로 그래프를 정렬해주지 않는다면, 결과값이 달라짐.

예제 시각화

해답

from collections import deque
import sys

def dfs(node):
    state[node] = 1 # 방문 노드는 방문 처리
    ans.append(node) # 그 후 append
    for nxt in graph[node]: # 다음 노드 list
        if state[nxt]==1: # 방문 했다면 
            continue # 방문 x
        dfs(nxt) # 방문 시작

def bfs(node):
    state[node] = 1 # 노드 방문 처리
    a=deque([node]) # 방문 처리된 노드는 큐에 추가
    while len(a): # 큐가 빌 때 까지
        node = a.popleft() # FIFO원칙에 따라 큐에서 node 제거
        ans_2.append(node) # 제거된 node는 방문하기에, ans에 추가
        for nxt in graph[node]: # 다음 노드 list
            if state[nxt]==0: # 방문하지 않았을 경우
                a.append(nxt) # 큐에 추가하고
                state[nxt]=1 # 방문처리
                
n,m,l = map(int, input().split()) # 입력
graph =[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)): # 탐색을 위해 노드 정렬
    graph[i] = sorted(graph[i])
    
state = [0 for i in range(n+1)] # dfs용 state
ans=[] # dfs 노드 방문 순서 list
ans_2=[] # bfs 노드 방문 순서 list
dfs(l) # 입력된 l노드부터 탐색
state = [0 for i in range(n+1)] # bfs용 state
bfs(l) # 입력된 l노드부터 탐색 

print(*ans) # dfs 출력
print(*ans_2) # bfs 출력