[Python] 백준 #2606 - 바이러스

문제

---

2606번: 바이러스

코드

---

My answer

import sys
input= sys.stdin.readline

def dfs(new_d):
    for i in new_d:
        if(visited[i]==0):
            visited[i]=1
            dfs(d[i])    
    return True

n=int(input())
connect=int(input())

visited=[0 for i in range(n+1)]
d=[[] for _ in range(n+1)]

for i in range(connect):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
visited[1]=1
dfs(d[1])

answer=visited.count(1)
print(answer-1)
#print(visited)

Another answer(DFS)

n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
def dfs(v):
    visited[v]=1
    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)
dfs(1)
print(sum(visited)-1)

Another answer(BFS)

import sys
from collections import deque
input= sys.stdin.readline

n=int(input())
connect=int(input())

visited=[0 for i in range(n+1)]
d=[[] for _ in range(n+1)]

for i in range(connect):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    
visited[1]=1
Q=deque([1])
while Q:
    c=Q.popleft()
    for nx in d[c]:
        if visited[nx]==0:
            Q.append(nx)
            visited[nx]=1
print(sum(visited)-1)

풀이

---

우선 이 문제는 dfs로 푸는 문제였다. (나중에 알고보니 DFS, BFS 모두로 풀 수 있다).

재귀를 이용하고자 했고 내 풀이방법부터 설명해보겠다.

[DFS 풀이]

우선 연결되어 있는 컴퓨터들을 입력받고 각 컴퓨터마다 연결되어 있는 컴퓨터를 가리키는 리스트를 생성한다. 

예를들면, 본문에 있는 예시를 입력받았을 때 d라는 리스트를 생성하고, 각 리스트 마다 연결되어 있는 컴퓨터를 저장할 것이다.

[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]] 이런식이다. 1번 컴퓨터에는 2번 5번이, 2번 컴퓨터에는 1,3,5번이 이런식. 리스트 인덱싱이 헷갈려서 d[0]은 비워놨다. 아무튼 이런식으로 저장한후에 d[1]부터 dfs()라는 함수를 생성하여 실행한다.

그럼 d[1] 즉 1번 컴퓨터 연결되어 있는 2,5번 컴퓨터를 반복문으로 돌면서 2번컴퓨터에 들어가서 또 dfs함수를 실행한다.그럼 2번에 연결된 1,3,5를 또 확인하는데 이때 1로 돌아가면 무한 루프가 돌기 때문에 visited라는 리스트를 통해 이미 확인한 컴퓨터인지를 저장한다. 따라서 이미 방문한 컴퓨터는 건너뛰고 이런식으로 모든 컴퓨터를 확인하게 되고

최종적으로 방문한 컴퓨터=visited에 1로 저장된 컴퓨터 들이 1번 컴퓨터에 의해 감염된 컴퓨터 들이다. 

[BFS 풀이]

bfs로 푸는 방법의 경우 잘 생각나지 않았다.

우선 dfs로 풀 때와 동일한 방법으로 리스트 d와 0으로 채워진 visited 리스트를 생성한다.

이후 que를 선언하고, 빈 큐에 첫번째 컴퓨터와 연결된 컴퓨터들을 넣는다.

이 후 첫번쨰 컴퓨터와 연결된 2번 컴퓨터를 거치면서, visited를 1로 만들어주고 que에 2를 추가한다. 이후 다시 첫번쨰 컴퓨터와 연결된 5번 컴퓨터를 거치고 visited[5]=1로 바꾸고, que에 5를 추가한다. 여기서가 dfs와 다른점인데 dfs에서는 2를 거치고 이제 2와 연결된 컴퓨터로 들어가는 깊이우선탐색이었고, bfs는 2거치고 que에만 넣어놓고, 5도 que에 넣고 1끝나면 이제 que에 있는 2를 들어가면서 진행된다. 

최종적으로 visited에 1로 채워진 것들의 합을 계산하고 첫번쨰 컴퓨터 1을 뺴주면 답이 된다. 

(설명이 어려웠다면 댓글달아주셔요.)

 

+) DFS와 BFS 두가지 방법으로 자세한 설명이 적혀있어 링크 남겨둡니다.

[DFS, BFS 설명 및 코드]

[백준] 2606 바이러스 - Python (그래프 탐색)

[다양한 방법]

[python] 백준 2606번 : 바이러스 (DFS, BFS)