[백준 - Python] 바이러스: 2606번

🥈 Silver3

 

https://www.acmicpc.net/problem/2606

 

 

✅ 정답풀이 : DFS

def dfs(idx):
    stack=[idx]
    #stack.append(idx)
    visited[idx]=True

    while stack:
        cur=stack.pop()
        for adj in graph[cur]:
            if not visited[adj]:
                visited[adj]=True
                stack.append(adj)




# 그래프 초기 설정
n=int(input())
graph=[[] for _ in range(n+1)] #0번째 인덱스는 빈배열로

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

# 탐색
visited=[False]*(n+1)
dfs(1)

# 1번노드 제외하고 방문한 노드 개수 카운트하기
result=0
for i in range(2,n+1):
    if visited[i]:
        result+=1
print(result)

 

1번 컴퓨터를 통해 바이러스가 전염되는 컴퓨터의 개수를 구하는 문제로, 1번과 연결되어 있지 않는 다른 그룹의 컴퓨터는 전염이 될 수 없다. DFS/BFS 어떤 방식으로든 그래프를 순회하게 될것이고 1번(start)를 제외한 방문한 노드개수를 카운트하면 된다.

 

메모리	실행시간
31120KB	40ms

 

 

✅ 정답풀이 : BFS

def bfs(idx):
    from collections import deque

    # idx인덱스 큐에 넣고 방문처리
    q=deque([idx])
    visited[idx]=True

    while q:
        idx=q.popleft() # 큐에서 제거
        # 인접 노드순회
        for i in graph[idx]:
            if not visited[i]:
                visited[i]=True
                q.append(i)


# 그래프 초기 설정
n=int(input())
graph=[[] for _ in range(n+1)] #0번째 인덱스는 빈배열로

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


# 탐색
visited=[False]*(n+1)
bfs(1)


result=0
for i in range(2,n+1):
    if visited[i]:
        result+=1
print(result)

 

메모리	실행시간
34052KB	72ms