(Python/🥈3)백준 알고리즘 2606번: 바이러스

문제출처: https://www.acmicpc.net/problem/2606

2606번: 바이러스

풀이:

bfs 형식

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


computer = int(input())
line = int(input())

graph = [[] for _ in range(computer+1)]

for i in range(line):
    start, end = input().split(" ")
    graph[int(start)].append(int(end))
    graph[int(end)].append(int(start))

Q = deque([1])

visited = [False] * (computer +1)
while Q :
    q = Q.popleft()
    for i in graph[q]:
        if visited[i] == False:
            Q.append(i)
            visited[i] = True
print(sum(visited)-1)

graph 에는 양방향이므로 양방향으로 가는 간선들을 넣어준다 .

[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]] 이런식으로 나온다

 

Q 에 시작지점인 1 을 넣어준다

 

Q가 있는동안에

시작지점이랑 연결된 곳인 i 를 뽑아서

만약 방문하지 않은 지점이라면 그 지점을 q에 넣는다 이유는 1이 2랑 연결되어있고 2가 3이랑 연결되어 있으면 3에도 가야하기때문이다

그리고 방문하였으니깐 true 로 바꿔준다

sum(visited) 해주면 true 에 갯수를 세어준다.

 

 

 

dfs 방식

 

 

graph , computer, line 은 그대로 사용

visitedd = [False] * (computer +1)
def BFS(depth):
    visitedd[depth] = True

    for v in graph[depth]:
        if visitedd[v] == False:
            BFS(v)
BFS(1)
print(sum(visitedd)-1)

 

깊이 우선 탐색은 주로 재귀함수를 이용하여 푼다. 연결된 자식 끝까지 들어가는것이다.

 

올림피아드 초등학교 지역본선 문제라고 한다 ,,