DFS, BFS

DFS

Depth-first search 깊이 우선 탐색

• 풀이 과정
  1. graph, 시작위치 v, visited 를 입력 받음.
  2. visited[v]에 방문 표시를 함
  3. graph[v] 리스트의 항목에 대해 방문한 적 없으면 dfs 재귀적으로 실행

• 백준 24479, 24480

# 24479, 24480
import sys

input = sys.stdin.readline # 빠른 입력 받기
sys.setrecursionlimit(10 ** 8) # 파이썬의 재귀 깊이를 늘려놓기

global order
order = 0

def dfs(graph, v, visited):
    global order
    order += 1
    visited[v] = order
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [0 for _ in range(n + 1)]

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

for i in graph:
    i.sort()
    # i.sort(reverse=True)

dfs(graph, r, visited)
for i in visited[1:]:
    print(i)

• 문제에서 i번째 줄에 i 원소에 도달한 순서를 출력하래서 순서 입력용 리스트를 추가로 만들었더니 메모리 초과, 시간 초과 남.
• visited에 순서 입력하는 방식으로 변경함. -> 전역변수 사용
• 파이썬은 재귀 깊이 제한이 작은 편이라서 sys.recursionlimit을 따로 지정하는게 좋다고 한다.

BFS

Breadth-first search 깊이 우선 탐색

• 풀이 과정
  1. from collections import deque
  2. graph, 시작위치 start, visited 를 입력 받음.
  3. queue 만들고, visited[v]에 방문 표시를 함
  4. queue 왼쪽에서 요소를 빼고, 해당 요소와 인접한 요소를 queue에 넣는 과정을 queue의 길이가 0이 될 때까지 반복
  
• 백준 24444, 24445

import sys
from collections import deque
input = sys.stdin.readline

def bfs(graph, start, visited):
    queue = deque([start])
    order = 1
    visited[start] = order
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i] == 0:
                queue.append(i)
                order += 1
                visited[i] = order

n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
for i in graph:
    i.sort()
    # i.sort(reverse=True)

bfs(graph, r, visited)
for i in visited[1:]:
    print(i)

• deque는 popleft
• 마찬가지로 sys.stdin.readline 으로 입력에 걸리는 시간 줄이기