[백준] 바이러스 풀이

DFS로 풀었습니다. 최대 범위가 100이라 상당히 여유로운 문제였습니다.

arr이라는 행, 열이 각각 (N+1)인 이차원 리스트를 만들었습니다.
N이 아닌 N+1로 만든 건, 코드의 가독성을 위해서입니다.
1번 컴퓨터가 0번 인덱스에 있는 것 보다는 1번 인덱스에 있는 게 낫다는 판단이었습니다.
visited라는 리스트 또한 N+1 크기로 만들었고, 0으로 초기화했고 방문 시 1로 값이 변합니다.

컴퓨터 번호를 2개씩 입력받고, 해당 인덱스와 행렬이 반대인 인덱스를 1로 바꿔줍니다.
즉, 1 2를 입력받으면 arr[1][2], arr[2][1] 를 각각 1로 만들면 됩니다.

DFS를 이용하여 순회하였고 순회 시에 해당 visited 인덱스를 1로 만들어서 다시 순회하는 일이 없도록 하였습니다.

1번 컴퓨터 순회 결과를 알면 되기에, DFS(1)을 해줬고,
visited 리스트에서 1의 갯수를 count함수를 이용하여 센 뒤, 1을 뺸 값을 print 해줬습니다.

이유는, 1번 컴퓨터에 의해 감염된 컴퓨터를 세는 것인데, visited 변수에는 1번 컴퓨터까지 포함되어 있기 때문입니다.

def DFS(x):
    visited[x] = 1

    for i in range(1, N + 1):
        if arr[x][i] == 1 and visited[i] == 0:
            DFS(i)


N = int(input())
arr = [[0 for i in range(N + 1)] for j in range(N + 1)]
M = int(input())
visited = [0] * (N + 1)

for i in range(M):
    a, b = map(int, input().split())
    arr[a][b] = 1
    arr[b][a] = 1

DFS(1)
print(visited.count(1) - 1)  # 1번 컴퓨터 본인 빼고 카운트

좋은 웹페이지 즐겨찾기