바이러스

❓문제

❗문제 정리

dfs사용, 방문노드를 출력하는 대신, count변수 값을 누적해줌.

📑코드

computers=int(input())#컴퓨터의 개수 - 노드
connected=int(input())#네트워크와 연결된 개수- 간선

graph=[[] for _ in range(computers+1)]
for i in range(connected):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited=[False]*(computers+1)
count=-1#시작노드 제외

def dfs(graph,v, visited):
    global count
    visited[v]=True#방문한노드 방문처리
    #print(v,end=' ')
    count+=1#방문한 노드의 개수 세기

    for i in graph[v]:#연결되어있는 노드
        if not visited[i]:#아직 방문하지 않았다면
            dfs(graph, i, visited)#dfs실행

dfs(graph, 1, visited)
print(count)

📝코드 설명

computers=int(input())#컴퓨터의 개수 - 노드
connected=int(input())#네트워크와 연결된 개수- 간선

graph=[[] for _ in range(computers+1)]
for i in range(connected):
    a,b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

필요한 파라미터 입력받기
computers(int) : 컴퓨터의 수(==노드의수)
connected(int) : 네트워크와 연결된 컴퓨터의 수(==간선의 수)
graph : 인덱스 노드와 연결된 노드 표시
a, b(int) : 연결된 컴퓨터(노드)
서로 연결되어있다고 하였으므로, 양방향 간선->서로의 인덱스에 자기 자신 노드를 넣어줌.

visited=[False]*(computers+1)
count=-1#시작노드 제외

방문처리 확인 변수 visited 만들고, 바이러스 걸린 컴퓨터의 개수를 셀 count변수를 만든다. 이때, 시작하는 컴퓨터의 개수는 포함하지 않으므로 -1로 초기화한다.

def dfs(graph,v, visited):
    global count
    visited[v]=True#방문한노드 방문처리
    #print(v,end=' ')
    count+=1#방문한 노드의 개수 세기

    for i in graph[v]:#연결되어있는 노드
        if not visited[i]:#아직 방문하지 않았다면
            dfs(graph, i, visited)#dfs실행

dfs 주석 참고, count를 global로 선언하였다. 재귀로 인해 count가 -1로 변하는 것을 방지.

dfs(graph, 1, visited)
print(count)

dfs 실행 후, 누적된 컴퓨터의 수count를 출력.

🎖제출 결과

💡insight