[BOJ] #2606 바이러스

바이러스

백준 #2606

---

📌 문제

예제 입력

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력

4

---

📌 풀이

Logic

• 컴퓨터 수 Com, 연결쌍의 개수 connect 입력 받기
• graph, visited 리스트 생성 <- 백트래킹(BackTracking)
  • graph 생성 시 (a, b) (b, a) 모두 추가 <- 무방향 간선
• BFS 함수 구현(deque)
  • 현재 위치에서 이동 가능한 노드 중, 아직 방문하지 않았다면,,,
  • deque에 추가 & cnt 증가(감염됨)

# 변수명
Com : 컴퓨터 수
connect : 간선의 수
graph : 노드 리스트
visited : 백트래킹을 위한 리스트

dq : 노드에 연결된 컴퓨터 번호를 저장하는 deque

Python

import sys
from collections import deque

def bfs(start, graph):
    dq = deque()
    dq.append(start - 1)
    visited[start - 1] = True
    cnt = 0

    while dq:
        current = dq.popleft()

        for edge in graph:
            a, b = edge[0] - 1, edge[1] - 1

            if a == current and not visited[b]:
                dq.append(b)
                visited[b] = True
                cnt += 1

    return cnt

Com = int(sys.stdin.readline())
connect = int(sys.stdin.readline())

graph = []
visited = [False] * Com

for i in range(connect):
    a, b = map(int, sys.stdin.readline().split())
    graph.append((a, b))
    graph.append((b, a))

print(bfs(1, graph))

---

✏️ 새로운 내용

-

---

📚 회고

💡 노드와 간선

• 해당 문제에서는 크게 걸림돌이 되지 않았지만, 트리 구조에서 간선의 방향에 대해 생각해 볼 필요가 있다.
• 탐색을 하는 과정에서 if/elif문을 사용하는 방식도 있었지만, 직관적으로 하기 위해 처음 graph를 생성할 때 (a, b) (b, a)를 모두 추가하였다.

  if a == current and not visited[b]:
    dq.append(b)
    visited[b] = True
    cnt += 1
  elif b == current and not visited[a]:
    dq.append(a)
    visited[a] = True
    cnt += 1