[Python] BOJ 1260 - DFS와 BFS(DFS, BFS)

www.acmicpc.net/problem/1260

기초적인 그래프 탐색 문제이다. (그 동안 배우지 않고 어려워보여서 손을 안대고 있었는데, 막상 강의를 듣고 스터디도 하면서 문제를 많이 풀어보니 할 만한 것 같다.)

그래프 탐색방법에는 크게 2가지가 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다.

 

DFS(Depth First Search)

 - 깊이 우선 탐색이란, 쉽게 말해 한 정점을 정해 끝까지 파고들어가는 방법이다.

 - 모든 노드를 방문하고자 할 때 이 방법을 쓴다.

 - 자기 자신을 호출하는 재귀방식을 사용한다.

 - 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수)

 단점

- BFS에 비해 조금 느리다.

- DFS는 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없다.

출처: https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(Breadth First Search)

- 너비 우선 탐색이란, 깊이 우선 탐색과 달리 넓게 탐색하는 방법이다.

- 최단 경로를 찾거나 임의의 경로를 찾고 싶을 때 이 방법을 쓴다.

- Queue 자료구조를 사용한다.

- 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수)

- 단순 검색 속도는 BFS가 조금 더 빠르다.

단점

- Queue에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.

- DFS는 코드가 간단해서 직관적이지만, BFS는 코드도 복잡하고 직관적으로 코드가 어떻게 돌아가는 지

  판단하기 힘들다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

# 그래프 탐색은 어떤 노드를 방문했는지 여부를 판단하는 배열을 사용해야 한다. 사용하지 않을 시

무한루프에 빠져서 시간초과가 뜨는 등 에러가 난다.

 

python 코드는 다음과 같다.

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

for i in range(m):
	# x와 y를 서로 연결해준다.
    x, y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
for l in graph:
    l.sort()

def dfs(v):
	# 깊이우선탐색
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

visited = [False] * (n+1)
dfs(v)
print()

def bfs(s):
	# 너비우선탐색
    queue = collections.deque([s])
    visited2[s] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited2[i]:
                queue.append(i)
                visited2[i] = True

visited2 = [False] * (n+1)
bfs(v)

 

(입대하고 틈틈이 공부를 했는데 뭔가 제대로 하고 있는 것 같지 않아 2021년 새해 기념으로 마음을 다시잡고

빡세게 공부중이다. 확실히 열심히 하니 이해가 되는것 같고 실력도 많이 늘어난 것 같다. 복습차원에서 다시 블로그 

포스팅을 해야겠다.)