[백준/파이썬] 2606번<바이러스> 문제 풀이

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

4

 

 

 

---

사고 흐름

1번 컴퓨터와 연결된 모든 컴퓨터의 개수를 구하는 문제

-> 그림에서 알 수 있듯이 그래프 탐색 문제라는 걸 알 수 있다

-> dfs를 쓸까? bfs를 쓸까?

-> 공부를 위해 dfs 사용!

 

문제 핵심과 알고리즘

한 정점에서 시작해 간선을 타고 이어진 모든 정점을 방문하는 그래프 탐색 문제이므로 dfs 또는 bfs 사용하자!

n, m=int(input()), int(input())
virus_list=[]
visited=[]

for i in range(m) :
    virus_list.append(list(map(int, input().split())))

def dfs1(v) :
    visited.append(v)

    for w in virus_list :
        if w[0]==v and w[1] not in visited :
            dfs1(w[1])
        elif w[1]==v and w[0] not in visited :
            dfs1(w[0])
dfs1(1)
print(len(visited)-1)

 

문제 풀면서 헤맸던 부분

1. 인접 정점 리스트

  처음 문제를 풀고 제출했는데 바로 틀렸다. 예제와 다른 케이스는 맞는 것 같은데.. 근데 잘 보니 virus_list에서 인접한 정점들을 가져올때 w[0]==v 이고 w[1]를 방문 안했으면 이라고만 했는데, 인접한 리스트 순서가 정해진 게 아니라서 이렇게하면 틀린다. 그래서 elif하고 w[1]와도 비교하는 코드를 추가했다. 

 => 방향이 없는 그래프라서 이런 문제가 생겼다. 주의하자!

 

다른 사람 풀이 참고해 배운 점

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)

이 풀이는 그래프를 생성했다. 두 숫자에 해당하는 index를 가진 그래프 정점에 각각 상대 정점을 추가했다. for문으로 그래프의 i 원소와 인접한 모든 노드들을 추가해 그래프를 만들었다. 그리고 시작 노드에 인접한 점들에 대해 방문하지 않았으면 dfs를 호출한다. 

 

총평 

dfs는 재귀 또는 스택으로 구현 가능하다. 기왕 코드를 암기하다시피하면 문제 풀이 속도가 정말 빠르니 암기하도록 하자!