2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
아이디어:
BFS 혹은 DFS로 그냥 그래프를 탐색하기만 하면 되는 간단한 문제이다.
BFS는 큐를 사용해야 되니까 귀찮아서 DFS로 탐색했다.
이제 조금 DFS를 구현하는 게 익숙해진 것 같다.
import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
visit = [False]*(N+1)
for _ in range(K):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
def dfs(x):
cnt = -1 #1번 컴퓨터의 감염은 카운트하지 않으므로
stack = []
stack.append(x)
visit[x] = True
while (stack):
n = stack.pop()
cnt+=1
for i in graph[n]:
if (visit[i]==False):
visit[i] = True
stack.append(i)
return cnt
print(dfs(1))
1번 컴퓨터로부터 감염된 컴퓨터의 개수를 세는 것이므로 1번컴퓨터는 감염으로 치지 않는다. 따라서 그냥 cnt의 초깃값을 -1로 주었다.
'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글
BOJ 19621번: 회의실 배정2 (0) | 2021.05.12 |
---|---|
BOJ 1987번: 알파벳 (0) | 2021.02.08 |
5829번: Luxury River Cruise (0) | 2021.02.08 |
BOJ 19538번: 루머 (0) | 2021.02.07 |
BOJ 1697번: 숨바꼭질 (0) | 2021.02.06 |