[내일배움캠프 20일차 TIL] 백준 2606 바이러스 with python - bfs/dfs

어제 트리의 부모찾기 문제를 꽤나 고생하며 풀어서 그런지 오늘 문제는 비교적 쉽게 풀었다

트리의 부모 찾기 문제보다 조금 더 정석적이고 쉬운 bfs/dfs라 그랬을지도...?

오늘은 두 가지 방법으로 문제를 풀어보려고 한다!

왜냐면 튜터님이 그러라고 했으니까...

 

---

백준 2606번 바이러스 문제는 다음과 같다

 

어제 문제와는 달리 비연결 그래프라는 것!

그리고 부모 노드를 출력하는 것이 아닌 1번 노드에서부터 연결된 노드들을 출력하는 것이다

조금 더 정석적인 깊이/넓이우선탐색 문제인 것이다

어제는 재귀로 깊이우선탐색을 풀었으니 오늘은 스택을 이용해서 깊이우선탐색을

그리고 큐를 이용해서 넓이우선탐색을 구현하고자 한다

 

 

 

 

---

스택을 이용한 깊이 우선 탐색(DFS : Depth First Search)

문제에 나와있는 예시를 가져와  1번에서 시작한 깊이 우선탐색은 1->5->6->2->3 순서일 것이다

4번과 7번은 연결되어있지 탐색하지 않은 것이고 감염되지 도 않게 되는 것이다

 

그럼 dfs를 구현하면 다음과 같다

# 깊이 우선 탐색
def dfs(tree, visited, stack):
    while stack: # 더 이상 방문할 곳이 없을 때까지
        now = stack.pop() # 스택의 가장 마지막 요소를 꺼내서
        if now not in visited: # 꺼낸 곳이 방문하지 않은 곳이라면
            visited.append(now) # 방문한 곳에 추가
            stack.extend(tree[now]) # 연결된 노드들을 방문할 곳에 추가
    return visited

 

tree는 딕셔너리 형태로 해당 노드를 key 값으로 하고 인접한 노드들을 집합 형태로 만들 것이다.

visited는 방문했던 노드를 담아두는 리스트이며

stack는 방문할 노드를 담아 둘 리스트이다.

이 문제에서는 1에서 바이러스가 시작해서 stack = [1] 로 코드를 작성했다

 

 

 

---

 

 

큐를 이용한 넓이 우선 탐색(BFS : Breadth First Search)

 

 

 

넓이 우선 탐색을 이용하면 1->2->5->3->6 순서가 될 것이다

 

bfs는 다음과 같이 구현하였다

def bfs(tree, visited, que):
    while que: # 더 이상 방문할 곳이 없을 때까지
        now = que.popleft() # 큐의 가장 첫 번째 요소를 꺼내서
        if now not in visited: # 꺼넨 곳이 방문하지 않은 곳이라면
            visited.append(now) # 방문한 곳에 추가
            que.extend(tree[now]) # 연결된 노드들을 방문할 곳에 추가
    return visited

 

여기서는 que만 달라졌는데 queue의 특징은 stack과 달리 선입선출이라는 것이다

따라서 que의 가장 앞에 있는 요소를 꺼내 반복문을 진행해준다

다른 부분은 깊이 우선 탐색과 같다

 

 

---

 

위의 코드를 이용하여 문제에서 주어진 입력값을 받아오고

입력값을 가지고 트리를 만든 후에 각각 깊이우선탐색과 넓이우선탐색을 이용하여 방문 경로를 출력해보았다

 

출력 코드는 다음과 같다

print("깊이 우선 탐색 방문 순서 : ",dfs(network, virus_dfs, will_visit_dfs))
print("넓이 우선 탐색 방문 순서 : ",bfs(network, virus_bfs, will_visit_bfs))

 

 

 

전체 코드는 여기서!

 

 

 

---

 

어제에 이어 오늘도 깊이/넓이우선탐색 문제를 풀다보니 좀 익숙해진것 같고, 이해도 좀 더 잘 되는 것 같다!

처음엔 왜 스택이니 큐니 재귀적으로 하는지 이해가 잘 안됐는데 몇 번 문제를 풀어보고 튜터님 설명도 듣고

디버깅 하며 오류도 수정해보니 점점 이해가 되어 가는 것 같다! 아직 응용 문제는 부족하지만 꽤나 잘 따라가고있다는 느낌이 든디!

아주 희망적이야!!!