69. Python 백준 2606 번 바이러스 자세한 설명
랜선에 연결된 컴퓨터가 감염이 되므로
DFS, BFS 를 통한 그래프 탐색으로 풀 수 있습니다.
시작 지점부터 그래프를 탐색하면서 방문하느 노드당 1개씩 카운트 해주면
연결된 컴퓨터들을 한번씩 방문하면서 카운트를 하게 되겠죠.
위의 직관으로 코드를 구현해봅시다.
저번과는 다르게 이번에는 리스트 형식으로 그래프를 표현해보겠습니다.
먼저 그래프를 표현할 리스트 graph와, 방문한지 안한지 체크하기 위한 리스트 visited 를 선언합니다.
graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
M개의 간선(랜선)이 있으므로 M 번 반복하며 graph리스트의 해당 인덱스에 [j] 리스트를 더해줍니다.
for _ in range(M):
i, j = map(int, input().split())
graph[i] += [j]
graph[j] += [i]
백준 2606번의 예제 입력이 들어왔을 때 graph 리스트를 확인해 볼까요?
인덱스에는 연결된 정점을 표시하는 리스트들이 저장되게 됩니다.
그리고 그래프 탐색을 위한 DFS를 구현해 줍니다,
먼저 시작 정점 V는 방문처리를 해주고
V와 연결된 리스트를 돌면서 아직 방문하지 않은 노드를 찾게되면
방문하며 재귀적으로 DFS를 실행하게 됩니다.
def DFS(V):
visited[V] = 1
for j in graph[V]:
if visited[j] == 0:
DFS(j)즉
1. 시작 노드 V를 방문처리 해주고
2. graph의 V 번째 인덱스에서 연결된 정점을 탐색하며 방문하지 않은 노드가 있다면
그 노드를 시작노드로 하여, 1번, 2번의 동작을 반복합니다.
위와 같은 과정을 반복하면 결국 그래프상 모든 노드를 깊이 우선 탐색으로 방문하게 됩니다.
그리고 방문했던 노드를 모두 1로 표시했으므로
방문했던 노드들을 다 더한 후 시작노드를 빼서 출력해주면 1번 컴퓨터를 통해 감염된 컴퓨터의 대수가 나오게 됩니다.
print(sum(visited) - 1)
Python 백준 2606 번 바이러스 최종 코드 입니다.
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
for _ in range(M):
i, j = map(int, input().split())
graph[i] += [j]
graph[j] += [i]
def DFS(V):
visited[V] = 1
for j in graph[V]:
if visited[j] == 0:
DFS(j)
DFS(1)
print(sum(visited) - 1)
Python 백준 2606 번 바이러스 이었습니다. 감사합니다.