[백준] 2606 - 바이러스 (python 파이썬)

백준 2606 문제 바로가기

풀이 코드

n = int(input())  # 컴퓨터의 개수
m = int(input())  # 쌍의 개수

graph = [[] for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)  # 서로 각자 연결되어있기 때문에 양쪽 다 넣어준다 ex) 1노드와 2가 연결되어 있으면 2노드랑 1노드와도 연결

# print(graph)

cnt = 0
visited = [0] * (n + 1)


def dfs(start):
    global cnt
    visited[start] = 1
    for j in graph[start]:
        if visited[j] == 0:  # 방문하지 않은 노드라면 
            cnt += 1
            dfs(j)  # 반복 재귀


dfs(1)
print(cnt)

이번주 알고리즘 스터디에서는 DFS에 관한 문제들을 집중적으로 풀기 시작했다. 그렇기에 최대한 DFS 알고리즘을 이용해 문제를 풀어보았다.

각 컴퓨터가 서로 연결되어 있기 때문에 각 컴퓨터마다 연결된 컴퓨터들을 서로 추가해줘야 한다. 처음에는 왜 n + 1을 한 2차원 배열을 생성해주는지 몰랐다가 각 행이 각 노드를 의미한다는것을 깨닫고 n+1한 2차원 배열을 생성해주는걸 이해했다.

로직으로는 2차원 배열에 입력값들을 삽입해주면 [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]] 와 같은 형태로 저장이 된다.
이후에는 dfs 함수를 통해 1번 행으로 갔을때 2번과 5번 컴퓨터를 탐색하고 2번으로 가서 3번과 5번, 3번으로 가서 2번, 5번으로 가서 1,2,6을 탐색한다.

기억하기

DFS 문제 풀이가 아직 익숙하지 않아서 바로 풀어지지가 않는다....
우선, 그래프를 통해 입력값들을 넣어준 후 시작점을 기준으로 탐색하고 탐색이 완료된 곳이라면 바꿔주기 !
모든 문제들이 같은 풀이는 아니겠지만 그래도 기본 메커니즘을 이해해야할듯,,