[백준] 1260번 DFS와 BFS

 

그렇습니다. DFS와 BFS입니다..ㅎㅎ

알고리즘을 공부하며 미루고 미루고 미루다가 직면했습니다..하하하

 

DFS(깊이우선탐색)과 BFS(너비우선탐색)은 코딩테스트에 필수적인 문제 중 하나라고 생각합니다.

알고리즘을 접하지 얼마되지 않았을때 너무 어려워서 외면했는데 최근 기업 공채 코딩테스트를 봐보니 이제는 마주할 때가 되었다고 생각했습니다.

---

DFS(Depth First Search)와 BFS(Breadth First Search)를 탐색 알고리즘입니다. 

데이터 속에서 원하는 데이터를 찾을 때 깊이와 너비를 우선적으로 고려하여 탐색하는 방법으로 차이를 둘 수 있습니다.

 

 

 

- DFS와 BFS 탐색 그래프

DFS // BFS

 

 

 

 

 

	DFS	BFS
탐색과정	현재 노드에서 갈 수 있는 끝까지 방문하여 탐색	현재 노드에서 연결된 노드를 방문 후 탐색
구현방법	스택 or 재귀 구현	주로 큐로 구현
라이브러리 활용	X	O (from collections import deque)
시간복잡도	일반적으로 동일, 재귀로 구현 시 DFS보다 BFS가 조금 빠르게 동작 N이 노드의 개수, E가 간선의 개수일 때 인접 리스트: O(N + E) 인접 행렬: O(N^2)
활용 문제	백트래킹	최단경로
	1. 그래프의 모든 노드 방문하는 문제 - DFS와 BFS 모두 가능 2. 경로의 특징을 저장하는 문제 - DFS (ex. a-b 이동시 같은 숫자가 있으면 안된다) 3. 최단거리 문제 - BFS

 

---

 

이제 다시 문제로 돌아와 풀어보겠습니다. 

풀이 순서는 다음과 같습니다.

1. 그래프를 맵핑

2. 그래프에서 낮은 숫자부터 탐색하도록 하기 위해 정렬

3. DFS( 재귀 활용)

4. BFS (큐 활용)

 

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

# 그래프 맵핑
for _ in range(m):
    s,e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

# 오름차순 정렬
for sub in graph:
    if sub :
        sub.sort()

# dfs
d_visited = [0]*(n+1)
d_ans = []
def dfs(num, graph, d_visited):
    if d_visited[num] == 0:
        d_visited[num] = 1
        d_ans.append(num)    
        for i in graph[num]:
            dfs(i, graph, d_visited)
dfs(v,graph, d_visited)

# bfs
from collections import deque
queue = deque([v])
b_visited = [0]*(n+1)
b_visited[v] = 1
b_ans = []

def bfs(graph, b_visited):
    while queue:
        num = queue.popleft()
        b_ans.append(num)
        for i in graph[num]:
            if b_visited[i] == 0:
                b_visited[i] = 1
                queue.append(i)
bfs(graph, b_visited)

print(*d_ans)
print(*b_ans)

 

 

 

아직 DFS와 BFS의 구현은 미흡하다고 생각합니다. 

관련 문제를 계속 풀어보며 연습해야겠다는 생각이 듭니다!!

 

 

1260번: DFS와 BFS

 

 

- 참고문서 : 파이썬 알고리즘 인터뷰

- 참고링크 : https://sunho-doing.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS