[Baekjoon, Python] 2606번 : 바이러스

도입

백준 단계별 풀기 DFS와 BFS 두 번째 문제이다.

---

백준 2606번 문제, 입력, 출력

---

백준 2606번 입출력 예제 1

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. DFS를 사용해서 풀었다. 재귀함수를 활용한다.

 

2. 인접한 노드를 방문할 때마다 list_visit의 인덱스를 1로 업데이트하고, for문을 통해서 1인 것들을 다 더해준다. 하지만, 문제에서 1번의 노드는 카운트를 하지 않기 때문에 최종적으로 결과값(rtn)에서 -1을 해준다. 나는 결과값(rtn)을 초기화 할때 -1로 설정함으로써 계산을 진행하였다.

---

코드

from sys import stdin

def dfs(V):
    list_visit[V] = 1               # 방문한 노드 1체크(나 방문했다!)
    for i in range(1, var_com + 1):   
        if list_visit[i] == 0 and inj_matrix[V][i] == 1:    # 방문하지 않고, 현재 노드에 인접한 노드 방문시 재귀
            dfs(i)      # 재귀

var_com = int(stdin.readline())
var_net = int(stdin.readline())
inj_matrix = [[0] * (var_com + 1) for i in range(var_com + 1)]  # 인접행렬 생성 (var_N +1 사이즈 만큼 행과 열)
list_visit = [0 for i in range(var_com + 1)]                  # 방문 정보 리스트 생성 (var_N +1 사이즈 만큼)

for i in range(var_net):  # 인접행렬 세팅         # 0 1 0 0 1 0 0
    x, y = map(int, stdin.readline().split())    # 1 0 1 0 1 0 0
    inj_matrix[x][y] = 1                         # 0 1 0 0 0 0 0
    inj_matrix[y][x] = 1                         # 0 0 0 0 0 0 1
                                                 # 1 1 0 0 0 1 0
dfs(1)                                           # 0 0 0 0 1 0 0
rtn = -1                                         # 0 0 0 1 0 0 0
for i in range(1,var_com+1):                    
    if list_visit[i] == 1:
        rtn += 1
print(rtn)

---

마무리

피드백은 언제든 환영이다^^