[백준] DFS와 BFS

문제

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

TC

• 인접 행렬을 사용한다면 O(V^2)
• 인접 리스트를 사용한다면 O(V+E)

Idea

입력 그래프를 n * n 인접 행렬에 저장했다.

1. DFS
   재귀함수를 사용해서 구현하였다.
   재귀 함수 종료 조건은 매 재귀에서 시작 vertex에 연결된 vertex가 없거나, 시작 정점으로부터 연결된 모든 vertex를 이미 방문한 경우이다.

반대로 탐색을 더 수행해야 되는 경우는 시작 정점으로부터 연결된 vertex가 존재하고, 연결된 vertex를 아직 방문하지 않은 경우이다.

2. BFS
   deque를 사용해서 구현하였다.
   deque에 시작 vertex를 추가하고, deque가 empty 할 때까지 반복하였다.
   deque에서 vertex를 하나 꺼내고, 꺼낸 vertex와 연결된 vertex가 존재하고, 해당 연결된 vertex를 방문하지 않은 경우 deque에 추가하는 방식으로 구현하면 된다.

CODE

from collections import deque

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

def bfs(graph, start, visited):
    queue = deque()
    queue.append(start)
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

# n=정점의 개수, m=간선의 개수, v=탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
# (정점의 개수 + 1) 크기의 배열 선언 -> 1번 인덱스부터 사용하기 위함
graph = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    # 입력으로 주어지는 간선은 양방향이다
    graph[x].append(y)
    graph[y].append(x)

# 방문할 수 있는 정점이 여러 개인 경우에는
# 정점 번호가 작은 것을 먼저 방문한다
for i in range(1, n+1):
    graph[i].sort()

# DFS
visited = [False] * (n+1)
dfs(graph, v, visited)
print()

# BFS
visited = [False] * (n+1)
bfs(graph, v, visited)

Self Code Review

DFS, BFS의 기본 문제라 막힘 없이 풀었다.
더 좋은 코드 작성 방법이 있을지 다른 코드들을 보며 확인해봐야겠다.