[백준] 2606번 바이러스 (Python)

문제

입출력, 예시

 

시간 복잡도, 공간 복잡도

컴퓨터의 수가 100대고 시간 제한과 메모리 제한은 아래와 같았다.

1 초

128 MB

 

파이썬은 1초에 2000만번 연산이 가능하다. N의 최대가 100이라는 것을 고려해봤을 때 시간복잡도는 여유롭다고 판단했다.

---

알고리즘

그래프가 주어졌고 "1번 컴퓨터가 감염되어서 2,3,5,6 컴퓨터도 감염된다."를 언급한 것으로 보아 그래프 탐색 유형임을 눈치챘다.

또한, 탐색 순서를 구체적으로 명시하지는 않았지만 감염 컴퓨터를 2,3,5,6으로 나열한 것으로 보아 DFS 탐색이라고 예상했다.

다음, 자연어 알고리즘과 코드다.

 

1. 입력을 받고 그래프를 만든다.

2. DFS로 그래프를 탐색한다.

3. 1번 컴퓨터로부터 감염된 컴퓨터를 출력한다.

 

# dfs 탐색
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
   

n = int(input()) + 1 # 컴퓨터의 수 (+1을 한 이유는 컴퓨터1을 인덱스1과 매칭시키기 위함이다.)
c = int(input()) # 쌍 개수
graph = [[] for i in range(n)] # 그래프

# 그래프 생성
for i in range(c):
    inp = list(map(int, input().split()))
    graph[inp[0]].append(inp[1])
    graph[inp[1]].append(inp[0])


# 방문기록테이블
visited = [False] * n

# 호출
dfs(graph,1,visited)

# 1번으로부터 감염된 컴퓨터 개수 출력, True는 감염
print(visited[2:len(visited)].count(True))

---

배운점(소감)

이 문제는 그래프 정보를 입력받아 그래프를 생성하고 그 그래프를 탐색하는 간단한 그래프 탐색 문제이다. 처음에 필자는 그래프를 생성할때 무방향 그래프인 것을 반영하지 않아 오답이 나왔다. 예를 들면, 노드1과 노드2가 연결되어 있으면 그래프 상에 (1,2), (2,1) 관계가 저장되어 있어야 했는데 나는 (1,2)만 저장했었다. 그래서 수정하기 위해 그래프 생성 코드를 아래와 같이 수정했다. 꼭 꼭 그래프의 특성(무방향 그래프)을 반영하자.

# 그래프 생성(무방향 그래프)
for i in range(c):
    inp = list(map(int, input().split()))
    graph[inp[0]].append(inp[1])
    graph[inp[1]].append(inp[0])