[파이썬/Python] 백준 2606번: 바이러스

숨·2024년 7월 15일

코테

알고리즘 문제 풀이

목록 보기

31/105

📌 문제 : 백준 2606번

📌 문제 탐색하기

com : 컴퓨터의 수 (1 ≤ com ≤ 100)
pair : 직접 연결된 컴퓨터 쌍의 수

✅ 입력 조건
1. com 입력
2. pair 입력
3. pair번 반복해 연결 정보 입력
4. 컴퓨터 번호는 1번 부터 차례로 매겨짐
✅ 출력 조건
1. 1번 컴퓨터로 바이러스 걸리는 컴퓨터 수 출력

한 컴퓨터가 웜 바이러스에 걸리면 그와 연결된 모든 컴퓨터가 걸리게 된다.
따라서 컴퓨터 연결 정보에 따라 1번 컴퓨터와 연결된 모든 컴퓨터를 찾아내 그 수를 출력하면 된다.

먼저, pair번 반복해 연결 정보들을 입력받아 저장한다.

1번부터 시작해 연결된 모든 컴퓨터를 찾아갈 것이기 때문에 DFS를 통해 재귀적 탐색한다.
차례로 연결된 컴퓨터를 거치면서 확인했다는 표시로 방문 처리 리스트를 만들어 따로 저장해준다.

DFS로 연결된 모든 컴퓨터를 돌면, 방문 처리 리스트에 1번 컴퓨터와 연결된 컴퓨터들을 확인할 수 있다.
방문 처리된 횟수를 세어 출력하면 원하는 바이러스에 걸린 컴퓨터 수를 찾을 수 있다.

가능한 시간복잡도

연결 정보 저장 리스트 생성 → $O(com)$
연결 정보 저장 → $O(pair)$
DFS → $O(com + pair)$
방문 처리 횟수 세기 → $O(com)$

최종 시간복잡도
$O(com + pair)$ 이므로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

DFS로 재귀적으로 연결 확인

📌 코드 설계하기

com 입력
pair 입력
연결 정보 저장할 리스트 정의
pair만큼 반복해 연결 쌍 저장
방문 처리 리스트 정의
dfs 구현
dfs 실행
방문 처리된 횟수 출력
원하는 형식 출력

📌 시도 회차 수정 사항

1회차

# 8. 방문 처리 안된 횟수 출력
count = 0

for v in visited:
    if v:
        count += 1

print(visited)

# 9. 원하는 형식 출력
print(count)

결과가 계속 1을 더한 값이 나왔다.
1과 연결된 컴퓨터 수를 출력해야 하는데, 방문 처리된 값을 내보내니 1까지 포함해 개수를 세어 발생한 문제였다.

# 8. 방문 처리 안된 횟수 출력
count = 0

for v in visited:
    if v:
        count += 1

print(visited)

# 9. 원하는 형식 출력
print(count-1)

count에서 1을 뺀 수를 출력하도록 했다.

2회차

# 9. 원하는 형식 출력
print(count-1)

결과
연결 정보가 하나도 없을 경우에 아무것도 방문 처리된 값이 없어서 0이 아닌 -1을 출력한다.

# 9. 원하는 형식 출력
if count == 0:
    print(0)
else:
    print(count-1)

출력 조건을 추가하여 해결했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. com 입력
com = int(input())

# 2. pair 입력
pair = int(input())

# 3. 연결 정보 저장할 리스트 정의
graph = [[] for _ in range(com+1)]

# 4. pair만큼 반복해 연결 쌍 저장
for _ in range(pair):
    # 시작점, 끝점 입력
    start, end = map(int, input().split())
    # 시작점, 끝점 양쪽에 연결 정보 추가
    graph[start].append(end)
    graph[end].append(start)

# 5. 방문 처리 리스트 정의
visited = [0] * (com+1)

# 6. dfs 구현
def dfs(c):
    # 해당 컴퓨터에 연결된 컴퓨터 확인해 방문 처리 안됐으면 방문 처리
    for i in graph[c]:
        if not visited[i]:
            visited[i] = 1
            # 재귀적 호출
            dfs(i)

# 7. dfs 실행
dfs(1)

# 8. 방문 처리 안된 횟수 출력
count = 0

for v in visited:
    if v:
        count += 1

# 9. 원하는 형식 출력
if count == 0:
    print(0)
else:
    print(count-1)