내코드

from collections import deque

com_num = int(input())
net_com_num = int(input())

dic = {}
for _ in range(net_com_num) : 
    a, b = map(int, input().split())
    if a in dic : # 존재하는경우
        dic[a].append(b)
    else : # 존재하지않는경우
        dic[a] = [b]
    if b in dic : 
        dic[b].append(a)
    else :
        dic[b] = [a]

visited = [False] * (com_num+1)

def bfs(start) :
    cnt = -1
    queue = deque([start])
    visited[start] = True
    while (queue) : 
        v = queue.popleft()
        cnt += 1
        visited[v] = True
        if v in dic :
            for _v in dic[v] :
                if visited[_v] == False : 
                    visited[_v] = True
                    queue.append(_v)
    return cnt


print(bfs(1))

클린코드

n = int(input())
m = int(input())

graph = [[0] * (n+1) for i in range(n+1)]
visited = [0] * (n+1)

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

result = []
def dfs(v):
    visited[v] = 1
    for i in range(1, n+1):
        if graph[v][i] == 1 and visited[i] == 0:
            result.append(i)
            dfs(i)
    return len(result)

print(dfs(1))

차이점

귀찮지만 dictionary로 구현하여 더 빠르게 돌리고싶었는데 오히려 더 느리게 나왔다.

• 사용 알고리즘
  - 나 : bfs
  • 모범 : dfs
• 사용 자료구조
  - grpah 정보를 기록
  - 나 : dictionary ( 더 빠를줄....)
  • 모범 : 2차원 list
• 시간
  - 나 : 136ms
  • 모범 : 88ms
• 코드 가독성
  - 모범이... 참좋다...^^......
  

분석

dfs/bfs 비교를 봤을때

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만 일반적으로 DFS를 재귀 함수로 구현한다는 점에서 DFS보다 BFS가 조금 더 빠르게 동작한다

라고 한다.

또한 DFS/BFS 사용 케이스 예시

• 그래프의 모든 정점을 방문하는 것이 주요한 문제

  • 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관이 없다.

• 경로의 특징을 저장해둬야 하는 문제

  • 예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다)

• 최단거리를 구하는 문제

  • 미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리하다.
  • 왜냐하면 DFS로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.

이외에도 검색 대상 그래프가 정말 크다면 DFS를 고려하고 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 고려하는 등으로 더 생각해볼 수 있다.

(출처 : 티스토리 서노리 [알고리즘 이론] 탐색 알고리즘 - DFS / BFS )