[백준 파이썬] 1260 DFS와 BFS

백준 1260

# 1260 / DFS와 BFS
from collections import deque

N, M, V = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

# 주어진 조건으로 인접 리스트 만들기
graph = [[] for _ in range(N+1)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

def dfs(V):
	# 낮은 순서부터 출력하기 위해 정렬, 스택을 사용할 경우 마지막 값부터 나오므로 reverse를 해준다
    for i in range(N+1):
        graph[i].sort(reverse=True)

    stack = [V]
    visited = [False] * (N+1)

    while stack:
        v = stack.pop()
		
        # 방문한 적이 없다면
        if not visited[v]:
        	# 방문하는 노드 출력
            print(v, end=' ')
            visited[v] = True
			
            # 연결되어있는 다음 노드 스택에 추가
            for next_v in graph[v]:
                if not visited[next_v]:
                    stack.append(next_v)

def bfs(V):
	# 낮은 순서부터 출력하기 위해 정렬
    for i in range(N+1):
        graph[i].sort()

    q = deque([V])
    visited = [False] * (N+1)
    visited[V] = True
	
    # dfs와 동일하다. 차이점은 스택이냐 큐나
    while q:
        v = q.popleft()
        print(v, end=' ')

        for next_v in graph[v]:

            if not visited[next_v]:
                q.append(next_v)
                visited[next_v] = True

dfs(V)
print()
bfs(V)

기본적인 깊이 우선 탐색과 너비 우선 탐색 과정을 작성하는 문제다. DFS는 보통 재귀함수로 구현했었는데 함수를 계속 호출하는 과정이 꽤 무겁다. 스택으로 구현하는 방법도 알아두는 것이 좋다고 생각해서 스택으로 구현해 봤다.