[Baekjoon] 1260번 : DFS와 BFS (Python)

Python

방법 1 - 메모리 33460KB / 시간 592ms / 코드 길이 793B

기본적인 DFS와 BFS를 위한 코드를 작성하였다.

DFS와 BFS 모두 방문했는지를 기반으로 구분에 들어간다.

DFS는 list를 기반으로 stack을 진행하고 필요에 따라 재귀를 활용한다.

stack은 append와 pop을 활용한다.

BFS는 deque라는 내장함수를 활용하고 queue를 기반으로 진행된다.

queue는 append와 popleft를 활용한다.

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

for i in range(m):
    a, b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)

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

# dfs
from collections import deque

visited = [False]*(n+1)
visited2 = [False]*(n+1)

# dfs
def dfs(graph, idx, visited):
    visited[idx] = True
    print(idx, end=' ')
    for i in graph[idx]:
        if not visited[i]:
            dfs(graph, i, visited)

# bfs
def bfs(graph, start, visited2):
    queue = deque([start])
    visited2[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')

        for i in graph[v]:
            if not visited2[i]:
                queue.append(i)
                visited2[i] = True

dfs(l, v, visited)
print()
bfs(l, v, visited2)

방법 2 - 메모리 38180KB / 시간 612ms / 코드 길이 633B

방법 1과 유사하나 메모리를 조금 더 사용한 방법이다.

본 방법은 입력받은 value를 저장해서 활용하는 것이 아닌 전체 n개에 대한 value 값이 존재하면 1을 지칭하게 하는 list를 입력받는다. 이는 많은 메모리를 활용할 수 밖에 없다. sparse

BFS를 위해서 별도의 내장함수가 아닌 list를 활용.

하나의 visit을 활용하기 위해 dfs에서 방문하면 0에서 1로 bfs에서 방문하면 1에서 0으로 바뀌는 방식을 선택한다.

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

for i in range(m):
    a, b = map(int, input().split())
    l[a][b] = l[b][a] = 1

visit = [False]*(n+1)

# dfs
def dfs(v):
    visit[v] = True
    print(v, end=' ')
    for i in range(1, n+1):
        if visit[i] == 0 and l[v][i] == 1:
            dfs(i)

# bfs
def bfs(v):
    queue = [v]
    visit[v] = False
    while queue:
        v = queue[0]
        print(v, end=' ')
        del queue[0]
        for i in range(1, n+1):
            if visit[i] == 1 and l[v][i] == 1:
                queue.append(i)
                visit[i] = False

dfs(v)
print()
bfs(v)