DFS와 BFS

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상✓

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

나의 풀이

import sys
from collections import defaultdict, deque

def DFS(graph,i,visited):
    visited[i]=True
    print(i,end=' ')
    for g in graph[i]:
        if not visited[g]:
            DFS(graph,g,visited)
        
def BFS(graph,i,visited):
    queue=deque()
    queue.append(i)
    visited[i]=True
    while queue:
        v=queue.popleft()
        print(v,end=' ')
        for g in graph[v]:
            if not visited[g]:
                queue.append(g)
                visited[g]=True

N,M,V=map(int,input().split())
graph=defaultdict(list)

for _ in range(M):
    n1,n2=map(int,sys.stdin.readline().strip().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
for key in graph:
    graph[key].sort()
    
visited=[False]*(N+1)
DFS(graph,V,visited)
print('')
visited=[False]*(N+1)
BFS(graph,V,visited)
print('')

• 위 문제는 단순히 BFS, DFS알고리즘을 구현하는 문제였다. 이제 BFS, DFS 알고리즘에 조금씩 익숙해져 가는 것 같다. 더 연습하면서 완전히 익숙해질 수 있도록 해야 할 것 같다.
• 특히 BFS의 deque()를 사용하는 알고리즘 방식을 잘 기억하자.