[파이썬] 2606번 '바이러스' 문제 풀이

[파이썬] 2606번 '바이러스' 문제 풀이

컴퓨터를 dfs 또는 bfs를 이용하여 탐색해보고 방문 처리가 안된 컴퓨터의 개수를 구하라는 간단한 문제입니다.

예제 예제에 대한 인접리스트

탐색 시 방문 처리가 될 때마다 count 하면 되는데 1번을 통해 걸리게 되는 컴퓨터의 수를 묻는 문제이기 때문에 1번을 제외하기 위해 최종적으로 나오는 count에 -1을 하여 해결합니다.

dfs를 이용한 풀이

count=0 def dfs(graph, v, visited): #깊이우선탐색 global count visited[v] = True #현재 노드 방문 처리 count+=1 for i in graph[v]: if not visited[i]: #방문 처리가 안된노드가 있다면 dfs(graph, i, visited) #방문 처리가 안된 노드를 들어가서 방문처리 N=int(input()) M=int(input()) graph=[[]for _ in range(N+1)] for _ in range(M): #인접리스트 구성 a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in graph: i.sort() visited = [False] * (N + 1) dfs(graph,1,visited) print(count-1)

bfs를 이용한 풀이

from collections import deque count=0 def bfs(graph,coord,visited): global count queue=deque([coord]) visited[coord]=True while queue: v=queue.popleft() count+=1 for i in graph[v]: if not visited[i]: queue.append(i) visited[i]=True N=int(input()) M=int(input()) graph=[[]for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in graph: i.sort() visited = [False] * (N + 1) bfs(graph,1,visited) print(count-1)

from http://lbdiaryl.tistory.com/187 by ccl(A) rewrite - 2021-10-22 19:26:48