[백준알고리즘] 1260번: DFS와 BFS -Python

[백준알고리즘] 1260번: DFS와 BFS -Python

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

DFS와 BFS를 한 문제에서 동시에 해결해야 하는 문제이다. 여러 경로가 가능한 경우 중에서 작은 번호의 정점을 우선 선택했을 때의 경로들을 출력하면 된다. 예에에에에전에 Java로 풀었던 적이 있는 문제이기도 하고 기본 DFS와 BFS를 복습할 겸 풀어보았다.

 

DFS(Depth First Search) 방식은 현재 정점에서 이동 가능한 정점들로 우선적으로 이동하면서 반복하기 때문에 스택을 사용한다. BFS(Breath First Search) 방식은 이동하면서 확인한다기보다는 레벨을 나눠 하나의 정점에서 이동 가능한 모든 정점들을 하나의 레벨로 두고 처리한다. 같은 레벨들을 먼저 처리하고 다음 레벨의 정점들을 처리하는 방식이기 때문에 큐를 사용한다.

 

문제를 풀 때에는 DFS의 스택을 위해 list()를 사용했고, BFS의 큐를 위해 deque()을 사용했다. deque()은 실제로는 양쪽으로 모두 삽입, 삭제가 가능한 자료구조이지만 그냥 간단하게 사용했다..

 

DFS와 BFS 모두 이전에 방문했던 정점인지 확인을 해주고 방문하지 않았었다면 방문하는 것으로 처리하고, 다음으로 처리할 정점들을 삽입한다. DFS는 이동가능한 정점들의 큰 값부터 삽입해서 작은 값들이 먼저 pop()할 수 있도록 했다. BFS는 하나의 레벨에서 작은 값부터 삽입해서 작은 값들이 먼저 poll 할 수 있도록 해주었다.

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())
link = []
for _ in range(N+1):
    link.append([0] * (N+1))

for _ in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    link[v1][v2], link[v2][v1] = 1, 1

def dfs(v):
    global visited
    visited = [0] * (N+1)
    seq = [v]
    res = []

    while seq:
        p = seq.pop()
        if not visited[p]:
            visited[p] = 1
            res.append(str(p))
            for i in range(N, 0, -1):
                if link[p][i]:
                    seq.append(i)
    return res

def bfs(v):
    global visited
    visited = [0] * (N+1)
    seq = deque([v])
    res = []

    while seq:
        p = seq.popleft()
        if not visited[p]:
            visited[p] = 1
            res.append(str(p))
            for i in range(1, N+1):
                if link[p][i]:
                    seq.append(i)
    return res


sys.stdout.write(' '.join(dfs(V)) + "\n")
sys.stdout.write(' '.join(bfs(V)))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다