[python] 백준 1260번: DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

곧 있을 LG 코딩테스트에 앞서 기본기 복습 겸, 가장 기본적인 DFS / BFS 문제를 풀어보았다.

 

특징은 DFS 는 재귀함수가 아니라 stack 을 활용해 만들었다는 것. (기본적으로 같은 반복횟수면 시스템상 재귀방식보다 stack 이 속도가 빠르다고 한다)

 

그리고 기존엔 visited 배열을 True Or False 로 했다면 여기선 visited 에 방문한 노드의 번호를 append 하는 방식으로 했다. 근데 이건 노드 갯수 n이 커지면 커질수록 T or F 방식에 비해 연산횟수가 늘어나는 문제점이 있을 듯.

 

왜냐면

V가 visited 에 있는지 검사하는 경우, T or F 방식이면 visited[V] is True or False 인지를 따지면 되니 O(1) 이지만

visited.append 방식이면 if V not in visited 조건문으로 처리해야하고 이러면 리스트의 모든 원소를 확인하게 된다.

 

하지만 당연히 공간차지는 후자가 더 적을 것이다. 하지만 둘다 큰영향은 없을 것.

 

코드

 

from collections import deque
import sys

input = sys.stdin.readline


n,m,v = map(int,input().split())
edges = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    if b not in edges[a]:
        edges[a].append(b)
    if a not in edges[b]:
        edges[b].append(a)

def DFS(start):
    stack = deque([start])
    visited = []

    while stack:
        now = stack.pop()
        if now not in visited:
            visited.append(now)
            temp = []
            for v in edges[now]:
                if v not in visited:
                    temp.append(v)
            temp.sort(reverse=True)
            stack += temp
    visited_str = [str(i) for i in visited]
    return ' '.join(visited_str)


def BFS(start):
    q = deque([start])
    visited = [start]

    while q:
        now = q.popleft()
        temp = []
        for v in edges[now]:
            if v not in visited:
                temp.append(v)

        temp.sort()
        q += temp
        for next in temp:
            visited.append(next)

    visited_str = [str(i) for i in visited]
    return ' '.join(visited_str)

print(DFS(v))
print(BFS(v))

 

DFS 에서 특기할 점은 스택 구조에 이웃 노드들의 역순으로 append 한다는 것. 스택은 LIFO (Last In First Out) 방식이므로 역순 정렬해 뒤에 붙여주어야 다음 차례에 마지막에 들어온 노드가 pop 되게 된다.

 

str.join 을 사용하기 위해선 iterable 객체의 원소가 str 형식이어야 하므로 

`[str(i) for i in visited]` 를 통해 visited 내의 integer 원소들을 str 로 바꾸어 처리했다.

 

BFS 에서도 평소엔 visited T or F 방식을 해왔지만 이번엔 방문 시 출력하지않고 리스트화해서 한꺼번에 출력하는 방식을 해봤다. 여기서도 노드의 번호가 낮은순으로 방문해야하기에 temp 배열에 이웃 원소들을 넣고 그 원소들을 정렬해 q 에 append 했다. 이부분을 생각못해 틀렸었다.