[boj] 바이러스_2606

# 바이러스

from collections import deque

# N은 노드의 개수
# M은 노드가 연결된 정보의 입력 횟수
N = int(input())
M = int(input())

# BFS알고리즘 활용을 위해 collections 모듈의 deque를 활용
queue = deque()
result = []

# 0번 인덱스는 활용하지 않고, 방문 여부를 체크해 줄 리스트 생성. 초기에는 모두 False이다.
visited = [False] * (N+1)

# 전체 그래프를 표현하기 위한 빈 리스트 생성
graph = [[] for _ in range(N+1)]

# 입력 정보를 이용해 그래프 생성을 위한 for 루프
for _ in range(M):
    i, j = map(int, input().split())
    # 일단 a-b 연결관계를 모두 입력 받아 a b노드 모두에 연결 정보를 저장한다
    graph[i].append(j)
    graph[j].append(i)

# 그래프 노드 연결 정보를 정렬하는 루프
for i in range(len(graph)):
    graph[i].sort()

# bfs알고리즘 함수
def bfs(par_graph, par_start, par_visited):
    queue.append(par_start)
    visited[par_start] = True
    while queue:
        temp = queue.popleft()
        result.append(temp)
        for i in par_graph[temp]:
            if not par_visited[i]:
                queue.append(i)
                par_visited[i] = True
                
# bfs 알고리즘 함수 실행                
bfs(graph, 1, visited)

# 결과 출력
print(len(result)-1)

2606번 바이러스 문제는 전형적인 bfs를 활용하는 문제였다.

 

이번 문제 역시 그래프는 빈 리스트를 포함하는 이중리스트로 구현했다. 0번 노드는 없으므로 0번 인덱스의 리스트는 사용하지 않았다.

위 방법으로 그래프를 구현하면 1번 인덱스의 리스트에는 1번 노드와 연결된 노드 번호를, 2번 인덱스의 리스트에는 2번 노드와 연결된 노드 번호를, ... 의 방법으로 그래프가 구현될 것이다. 이렇게 표현하는 것이 가장 보기 좋은 것 같다.

 

큐에 들어간 노드들은 연결 처리되는 노드이므로 이를 result 라는 리스트에 담아 그 길이를 출력하되, 1번 노드는 제외하므로 결과에서 -1 한 값을 출력해주었다.

 

딱히 구현에 어려운 부분이 있지는 않았으나 bfs 알고리즘 부분을 구현할 때 원활하지 않이 포스팅을 통해 다시 개념을 정리할 계획이다.

 

+) 코드를 작성하고 '만약 노드 연결정보가 중복되면(ex. 7 6이 입력되고 다시 7 6이 입력되는 경우) 그래프에서 연결 정보가 중복되어 문제가 발생하지 않나?' 하는 의문이 들었으나, 그래프의 각 인덱스에 해당하는 리스트에서 값을 이용해 확인 여부를 visited 리스트에 체크해 주므로 노드 연결 정보가 중복되어도 문제가 없이 동작한다.

 

※ 해당 게시물은 개인 코딩 공부를 위해 작성하는 글입니다. 문제가 있을 경우 dusrlf2003@naver.com으로 연락주세요!