Backjoon_2606 바이러스_Python풀이

바이러스_2606

[문제]

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

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

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

[입력]

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

[출력]

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

[TastCase]

[입력]

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

[출력]

4

[알고리즘 분류]

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

[문제 요약]

1. 총 컴퓨터 개수 입력
2. 연결된 컴퓨터 개수 입력
3. 1번 컴퓨터와 연결된 컴퓨터 개수 출력
4. DFS / BFS 선택해서 풀이 (본인은 DFS로 풀이)

[사용 알고리즘]

그래프 탐색이란?

• 정점에 있는 노드를 시작으로 모든 노드를 방문하는 탐색 기법

DFS(Depth First Serch)

• 스택 또는 재귀 호출을 이용한 알고리즘
• 깊이 우선 탐색 이므로, 가장 좌측 수칙으로 우선 탐색
• 조건에 해당하지 않은 노드를 발견 시 가장 가까운 갈림길로 돌아와 우측으로 한 칸씩 이동하며 다시 탐색
• BFS(너비 우선 탐색)에 비해 간단하지만 느림
• 주로 모든 노드를 탐색할 때 사용

BFS(Breadth First Serch)

• 이번 문제에선 사용하지 않았지만 DFS랑 같이 학습하기 좋은 알고리즘
• 큐 또는 재귀 호출을 이용한 알고리즘
• 너비 우선 탐색 이므로, 수직이 아닌 수평을 기준으로 이동
• 즉, 가장 가까운 노드를 먼저 탐색
• 주로 특정 장소에서 다른 장소로 이동이 가능한지 알아볼 때 사용

#DFS풀이
def DFS(value) : # DFS 함수
    global result # 개수 카운트
    recursion[value] = 1 # 해당 벨류 인덱스의 값 1로 저장

    for i in computer[value] : # 리스트의 벨류 인덱스 값 까지 반복 
        if recursion[i] == 0 : # 첫 방문 시
            DFS(i) # 재귀
            result += 1 # 카운트

# 변수
result = 0
N = int(input()) # 총 컴퓨터 개수
link = int(input()) # 연결된 컴퓨터 개수
computer = [[] for _ in range(N+1)] # append를 사용하므로 모두 null로 만들기
recursion = [0] * (N + 1) # 모두 0으로 초기화

for i in range(link) : # link만큼 반복
    fnt, bak = map(int, input().split()) # 입력 값을 공백 기준으로 나누고 해당 값을 int형으로 fnt, bak에 저장
    computer[fnt].append(bak) # 서로 값을 넣으며 연결
    computer[bak].append(fnt)

DFS(1) # 1번 컴퓨터 고정
print(result) # 결과값 출력

[풀이 요약]

1. result 변수를 0으로 초기화하고, 컴퓨터 개수 N과 연결된 컴퓨터 개수 link를 입력 받는다.
2. 컴퓨터들 간의 연결 정보를 저장하기 위해 2차원 리스트 computer를 생성하고, 방문 여부를 체크하기 위한 1차원 리스트 recursion을 생성한다.
3. 연결 정보를 입력받아 computer 리스트에 저장한다.
4. computer[fnt] 리스트에 bak를 추가하고, computer[bak] 리스트에 fnt를 추가하여 양방향으로 연결 정보를 저장한다.
5. DFS 함수를 호출하여 연결된 컴퓨터들을 탐색한다.
6. 이 때, DFS(1)을 호출하여 1번 컴퓨터를 기준으로 탐색을 시작한다.
7. DFS 함수에서는 현재 value 컴퓨터와 연결된 컴퓨터들을 재귀적으로 탐색하며, 방문한 컴퓨터들을 recursion 리스트에 체크한다.
8. result 변수를 증가시키면서 탐색된 컴퓨터의 개수를 세어준다.
9. 탐색이 완료되면 result에 최종적으로 탐색된 컴퓨터의 개수가 저장되고, 이를 출력한다.

알아두면 좋은 Python문법!!

1. map(function, iterable)
   • function: 적용할 함수. 각 요소에 이 함수가 적용된다.
   • iterable: 순회 가능한(iterable) 데이터 구조. 리스트, 튜플, 문자열 등이 올 수 있다.
   • iterable의 값을 function형태로 바꾸어 저장해준다.
   • ex) fnt, bak = map(int, input().split())
     - 입력 받은 값을 공백 기준으로 나누어 int형으로 fnt, bak에 각각 저장