[BOJ][Python]2606번 풀이

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

2606번: 바이러스

from collections import deque

n = int(input())
p = int(input())
graph =[list(map(int, input().split())) for _ in range(p)]
visited = [False for _ in range(n+1)]
q = deque()
visited[1]=True
q.append(1)
while q:
    v = q.popleft()
    #print(v)
    for i in range(p):
        if graph[i][0] == v:
            if visited[graph[i][1]] == False:
                q.append(graph[i][1])
                visited[graph[i][1]] = True
        elif graph[i][1] == v:
            if visited[graph[i][0]] == False:
                q.append(graph[i][0])
                visited[graph[i][0]] = True
            
print(sum(visited)-1)

저는 노드가 거꾸로 연결되어있는 경우를 체크하지 않아서 약간 헤맸습니다. 원래 bfs를 어려워 하기도 했는데 뭔가 혼자서 풀어내니까 뿌듯하네요. 해당 문제와 비슷한 문제 중에 아직 못 푼 문제가 있는데 자고 일어나서 도전해봐야겠습니다. 약간 즐거워졌네요.

 

사실 알고 보면 bfs의 기본 중의 기본같은 문제인데요. 저 또한 컴퓨터 공학 전공도 아니고 알고리즘 공부를 맨땅에 헤딩하는 방식으로 하고 있는 사람으로서 해당 문제를 풀기 위해 했던 생각을 정리해보겠습니다.

 

설명에 앞서서 기본적인 bfs의 흐름에 대해서 간략하게 짚어보겠습니다. bfs는 dfs와 다르게 인접 노드를 타고 타고 깊숙하게 들어가는 방식이 아닌 현재의 노드에서 인접한 노드를 먼저 다 들르고 그 다음으로 노드를 하나 선택해서 해당 노드에서 인접한 노드를 다시 다 들르는 방식을 반복하는 탐색 방법입니다. 가령 원형의 방의 중심에서 벽에 있는 문을 통해서 모든 연결된 방들을 탐색한다고 가정하면 bfs는 원의 중심에서 가장 가까운 문을 전부 연 다음(문을 열어놓은채로)에 맨 처음에 열었던 방에 들어가서 그 방안에 있는 모든 문을 여는 걸 반복하는 방법이죠.

 

BFS(Breadth First Search) 요약 : 

1. queue에 맨 앞에 들어있는 원소(노드)를 꺼낸다.

2. 해당 노드와 인접한 노드를 전부 방문 처리 후, queue에 넣는다(별다른 언급이 없다면 보통 숫자가 작은 순서대로).

3, 더 이상 queue에 넣을 노드가 없다면 queue가 텅 빌 때 까지 다시 1번으로 돌아간다.

 

2606번의 예시를 가져와보면 먼저 1번을 queue에서 꺼내고 1번과 연결된 2,5 노드를 추가하고 방문 처리를 합니다. 더 이상 추가할게 없으니 다시 2번 노드를 꺼내고 2번과 연결된 3번 5번을 넣어야 하는데 이미 5번은 방문 처리가 되어있으니 3번을 넣고 방문 처리를 합니다. 그 다음엔 5번을 꺼내고 6번을 추가하고 방문 처리를 합니다. 그 다음엔 3번을 꺼내고 연결된 노드가 2번 하나 뿐이지만 2번은 이미 방문 처리를 했으니 아무것도 추가하지 않고 끝납니다. 6번도 마찬가지로 5번은 이미 방문처리가 되었으니 6번만 꺼내고 종료합니다. 4,7은 1과 연결된 노드들과 이어져있지 않기 때문에 큐에 삽입되지 않습니다.

 

여기서 놓치지 않아야 하는 부분이 있습니다. 저도 해당 부분을 놓쳐서 약간 헤맸는데요.

for i in range(p):
    if graph[i][0] == v:
        if visited[graph[i][1]] == False:
            q.append(graph[i][1])
            visited[graph[i][1]] = True
    elif graph[i][1] == v:
        if visited[graph[i][0]] == False:
            q.append(graph[i][0])
            visited[graph[i][0]] = True

이 부분입니다. 주어지는 간선이 항상 순서대로 되어있지는 않아요. 예를 들면,

10
7
1 2
2 3
3 4 
5 6
7 8
8 9
9 1

해당 반례는 5와 6을 제외하고 형태를 표시해보면 4-3-2-1-9-8-7 이런 그래프가 나옵니다. 하지만 순서대로만 탐색하도록 작성하면 당연히 1 오른쪽으로 나오는 노드를 체크하지 못하겠죠(인접 행렬로 푸신 분들은 아마 이런 문제를 겪진 않으실겁니다). 그래서 그런 부분을 해결하기 위해서 조건문을 이용해서 풀었습니다.

 

사실 인접 행렬을 사용하지 않았던 것은 약간 고집이었는데요. 왜 사용하는지도 모르면서 그냥 남의 코드를 따라하고 싶지는 않았습니다. 다만 이렇게 직접 bfs를 구현해보니까 왜 사람들이 인접행렬을 사용하는지 알게 되더라구요.

 

글이 약간은 도움이 되셨나요? 저도 항상 bfs를 제대로 풀지 못한다는 느낌이 있었지만 이번 문제로 약간은 해소된 것 같아 기분이 좋은데요. 조금 두서없는 글이긴 하지만 해당 포스팅에서 bfs에 대한 감을 좀 잡으셨다면 좋겠습니다.참고로 해당 문제는 dfs로도 풀 수 있습니다. 제 개인적인 생각으로는 dfs가 좀 더 쉽게 풀릴 것 같아요.