🤔 문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
첫째 줄에는 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다.
DFS(Depth-First Search)
- DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- DFS는 Stack or 재귀 함수를 이용한다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
def dfs(graph, v, visited) :
visited[v] = True
print(v, end = ' ')
for i in graph[v] :
if not visited[i] :
dfs(graph, i, visited)BFS(Breadth-First Search)
- BFS는 너비 우선 탐색, 그래프에서 가까운 노트부터 우선적으로 탐색하는 알고리즘이다.
- BFS는 Queue를 이용한다.
- 탐색 시작 노드를 Queue에 삽입하고 방문 처리를 한다.
- Queue에서 노드를 꺼낸 뒤에 해당 노드의 인접노드 중에서 방문하지 않는 노드를 모두 Queue에 삽입하고 방문처리를 한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
- BFS에서 주의해야할 점은 시작할 떄, queue안에 시작하는 정점의 번호인 V를 넣어주지 않으면, 이것은 맨 나중에 들어오게 된다. 그래서 문제의 요구를 충족시키기 위해서는 queue에 넣고 방문했다고도 check를 해주고 시작하는 것이 맞다.
visited1[V] = True
queue = deque([V])
print(V, end= ' ')
while queue :
q = queue.popleft()
for k in graph[q] :
if visited1[k] == False :
queue.append(k)
print(k, end = ' ')
visited1[k] = True
print()초기 설정
- N은 정점을 의미, M은 그 정점 사이를 이어주는 선의 갯수, V는 시작하는 번호를 의미한다.
- graph는 N+1개 만큼 empty list를 만들어 준다. 2차원 배열로 생성한다.
- N+1개인 이유는 0번으로 시작하는 정점은 존재하지 않기 때문에, 일부로 한 개를 더 만들어준다.
- visited의 경우에는 마찬가지로 1~N 까지 만들어 줘야 하기 때문에 역시 n+1개를 만들어 준다. 초기에는 모두 False로 설정해서 만들어준다. 방문하면 True, 아직 방문하지 않으면 False
- 한 방향이 아니라 양방향이기 때문에 연결시켜준다.
- 여기서 중요한 것이 정점 번호가 작은 것을 먼저 방문해야 하기 때문에, 각 list 별로 sort를 해서 낮은 순서대로 정렬해준다.
N, M, V = map(int, input().split())
graph = [[] for i in range(N+1)]
for pair in range(M) :
a,b = map(int, input().split())
graph[a]+=[b]
graph[b]+=[a]
for i in range(len(graph)) :
graph[i].sort()
visited = [False] * (N +1)
visited1 = [False] * (N +1)📝 느낀점 🥴
DFS와 BFS는 알고리즘 수업시간에 접해보았음에도 불구하고, 다시 공부해야 하는 상황이었다... 특히나 재귀함수에 약한 나로써는 DFS가 어렵게 느껴졌다. 그래도 기본적으로 이런식으로 구성된다는 것을 알게되었다. 앞으로 조금 더 심화한 문제들을 더 풀어가면서 DFS와 BFS에 대해서 조금 더 공부해 나갈 것이고, 어떤 문제에 DFS와 BFS를 적용하는 것이 더 좋을 지에 대한 문제도 계속해서 해결해 나갈 예정이다.
참고
https://bio-info.tistory.com/152
https://www.youtube.com/watch?v=7C9RgOcvkvo
Viel Erfolg!