[백준] 1260. DFS와 BFS (Python)

이번에 풀어 볼 문제는 <백준 1260번. DFS와 BFS>이다.

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

 

📌 문제 탐색하기

목표

• 그래프를 DFS와 탐색한 결과와 BFS로 탐색한 결과 출력하기

해야 할 것

1. DFS 함수 구현하기
2. BFS 함수 구현하기

입력

• N : 정점의 개수 ( 1 ≤ N ≤ 1,000 )
• M : 간선의 개수 (1 ≤ M ≤ 10,000)
• V : 탐색을 시작할 정점의 번호
• ( 정점, 정점 ) 으로 간선 나열

아이디어

• DFS 는 재귀를 활용해서 구현하고, BFS는 deque을 활용해서 구현해봐야겠다.
• 그래프는 { 정점1 : [] , 정점1 : [] }  형식의 인접리스트로 저장하자.
• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기! 
  ➡️정점 1 : [] value에 오는 리스트를 오름차순 정렬해두기

📌 코드 설계하기

1. input 입력받고 그래프를 딕셔너리를 활용한 인접 리스트로 저장한다.

2. 딕셔너리의 value에 오는 리스트를 오름차순 정렬해두기 ( 정점 번호가 작은 것부터 방문할 수 있도록)

3. DFS 함수 구현하기

def dfs(start_v, visited=[]):
    cur_v = start_v
    visited.append(cur_v)
    for next_v in graph[cur_v]:
        if next_v not in visited:
            visited = dfs(next_v, visited)
    
    return visited

 

4 . BFS 함수 구현하기

def bfs(start_v, visited =[]):
    visited.append(start_v)
    queue = deque(start_v)
    while queue:
        cur_v = queue.popleft()
        for next_v in graph[cur_v]:
            if next_v not in visited:
                visited.append(next_v)
                queue.append(next_v)
    
    return visited

 

5. dfs가 반환한 visited, bfs가 반환한 visited 순서대로 출력하기

📌 정답 코드

import sys
from collections import deque

N, M, V = map(int,sys.stdin.readline().split())

graph = {i:[] for i in range(N+1)} #O(N)

for _ in range(M): #O(M)
    a , b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1): #O(M log M)
    graph[i].sort()

def dfs(start_v, visited=[]): #O(N + M)
    cur_v = start_v
    visited.append(cur_v)
    for next_v in graph[cur_v]:
        if next_v not in visited:
            visited = dfs(next_v, visited)
    
    return visited

def bfs(start_v, visited =[]): #O(N + M)
    visited.append(start_v)
    queue = deque([start_v])
    while queue:
        cur_v = queue.popleft()
        for next_v in graph[cur_v]:
            if next_v not in visited:
                visited.append(next_v)
                queue.append(next_v)
    
    return visited

result_dfs = dfs(V)
result_bfs = bfs(V)

print(" ".join(map(str,result_dfs)))
print(" ".join(map(str,result_bfs)))

📌 알게 된 것

• queue는 리스트로도 , deque으로도 구현할 수 있지만 deque로 구현하는 것이 시간복잡도 측면에서 효율적이다.
  예를 들어 pop() 연산의 경우 리스트는 맨 앞 원소를 뺀 다음 한 칸씩 앞으로 땡겨야 하여 O(n) 만큼의 시간이 필요하지만, deque은 linked list로 구현되어 있으므로 O(1)이면 충분하다.
• dfs 와 bfs의 기본적인 시간복잡도는 O( 정점의 개수 + 간선의 개수 ) 이다.
• "구분자".join(이터러블)
• 리스트의 원소가 숫자일 경우, "구분자".join(map(str,리스트)) 형식으로 사용 가능