[백준] 2606 바이러스 (실버3) / DFS

문제요약

나의 코드 및 설명

• graph : 크기가 전체 컴퓨터의 개수 + 1 인 리스트를 초기화하고, for 문을 수행하여 각 노드가 연결된 정보를 2차원 리스트로 표현한다.
• visited : 바이러스에 감염된 컴퓨터 번호를 저장하기 위한 리스트
• dfs(graph, x, visited) : dfs(x)로 작성하여도 정상동작한다. 현재 노드를 방문처리하고, 노드와 연결된 다른 노드를 방문처리 하기 위해 for문을 수행한다. (재귀함수)

computer = int(input())
connect = int(input())

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

#각 노드가 연결된 정보를 2차원 리스트로 표현
for _ in range(connect):
    a,b = map(int, input().split())
    graph[a].append(b)
    if a not in graph[b]:
        graph[b].append(a)

#바이러스 방문 정보 리스트
visited = [0] * (computer + 1)

def dfs(graph, x, visited):
    #현재 노드를 방문처리한다.
    visited[x] = 1
    #노드와 연결된 다른 노드를 방문처리하기 위해 for문을 수행한다.
    for c in graph[x]:
        if visited[c] == 0:
            dfs(graph, c, visited)
    #재귀 함수가 끝나면 visited 리스트의 요소가 1인(방문처리) 개수를 리턴한다. 
    return visited.count(1)-1

print(dfs(graph, 1, visited))

다른 코드 및 설명

def dfs(x):
    #현재 노드를 방문처리한다.
    visited[x] = 1
    #노드와 연결된 다른 노드를 방문처리하기 위해 for문을 수행한다.
    for c in graph[x]:
        if visited[c] == 0:
            dfs(c)
     
print(visited) # >> [0, 0, 0, 0, 0, 0, 0, 0]
dfs(1)
print(visited) # >> [0, 1, 1, 1, 0, 1, 1, 0]
print(visited.count(1)-1)

cnt = 0

def dfs(x):
    global cnt
    visited[x] = 1
    for c in graph[x]:
        if visited[c] == 0:
            dfs(c)
            cnt += 1
            
dfs(1)
print(cnt)

피드백

문제의 조건에 해당하는 모든 노드를 방문처리해야 한다고 생각했기 때문에, DFS(깊이 우선 탐색)을 통해 문제를 해결해야된다고 확신했다.