문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력

4 5 1 # 정점의 개수, 간선 번호 시작 번호
1 2
1 3
1 4
2 4
3 4

예제 출력

1 2 4 3
1 2 3 4

내 풀이

! 작은 것부터 탐색하기만 하면 된다.

# DFS 아이디어

st.append(start)

반복(스택이 안비어잇으면) :
	스택에서 노드 꺼내기 (후입선출)
	스택에서 꺼낸게 방문처리되어있는 경우: 
		패스
	스택에서 꺼낸게 미방문인 경우: 
		노드 방문 처리
		노드에 필요 동작
		스택에 <-- 노드 넣기 (역순으로) 
		
# BFS 아이디어
큐에 시작 노드 넣기 

반복 (큐가 안비어져있으면) : 
	큐에서 노드 꺼내기 (선입선출, 앞에서 꺼내기) 
	노드 방문이면 : 
		패스
	노드 미방문이면 : 
		노드 방문 처리
		노드에 필요 동작 
		큐에 <-- 노드 넣기 (원래 순서대로) 

아이디어

정답 코드

import sys
from collections import deque

stack = deque()
queue = deque()

input = sys.stdin.readline

n,m,start = map(int,input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m) :
    s,e = map(int,input().split())
    graph[s].append(e)
    graph[e].append(s)

# graph.sort() => 전체 리스트 정렬이 되어버린다 (인데스 기준 연결 리스트 위치가 바뀜)

for i in range(1, n+1):
    graph[i].sort()

dfs = []
bfs = []

stack.append(start)

v_s = [0] * (n+1)

while stack :
    v = stack.pop()
    if v_s[v] == 0 : # 미방문일때
        v_s[v] = 1
        dfs.append(v)
        stack.extend(reversed(graph[v]))

print(" ".join(map(str, dfs)))

queue.append(start)
v_q = [0] * (n+1)

while queue:
    v = queue.popleft()
    if v_q[v] == 0 : # 미방문일때
        v_q[v] = 1
        bfs.append(v)
        queue.extend(graph[v])

print(" ".join(map(str, bfs)))