[백준] 2606 바이러스 - Python (그래프 탐색)

백준 로고

 

 

 

Contents

---

 

1. 문제 정의 및 예제 해석

(문제 링크: https://www.acmicpc.net/problem/2606)

2606번: 바이러스

주어진 컴퓨터에 대해, 1번 컴퓨터와 연결된 컴퓨터가 총 몇 개인지 출력하는 문제입니다.

예제를 보겠습니다.

7 : 총 컴퓨터의 대수입니다.

6 : 컴퓨터 간에 연결된 선의 개수입니다.

1 2 : 1번 컴퓨터와 2번 컴퓨터가 연결되었다는 의미입니다.

2 3

...

4 7

-> 입력을 바탕으로 컴퓨터 간의 연결을 시각화하면 아래와 같습니다.

컴퓨터간 연결 시각화

1번 컴퓨터와 연결된 컴퓨터는 2, 3, 5, 6번입니다. 그래서 출력은 4입니다.

 

2. 전체 코드

1) BFS(너비 우선 탐색)

from collections import deque
n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
    c=Q.popleft()
    for nx in graph[c]:
        if visited[nx]==0:
            Q.append(nx)
            visited[nx]=1
print(sum(visited)-1)

 

2) DFS(깊이 우선 탐색)

n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향
def dfs(v):
    visited[v]=1
    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)
dfs(1)
print(sum(visited)-1)

 

3. 해설

1) 입력 및 그래프 생성

n=int(input()) # 컴퓨터 개수
v=int(input()) # 연결선 개수
graph = [[] for i in range(n+1)] # 그래프 초기화
visited=[0]*(n+1) # 방문한 컴퓨터인지 표시
for i in range(v): # 그래프 생성
    a,b=map(int,input().split())
    graph[a]+=[b] # a에 b 연결
    graph[b]+=[a] # b에 a 연결 -> 양방향

n에는 컴퓨터 개수를 입력받고, v에는 연결선의 개수를 입력받습니다. graph는 n+1개만큼 빈 리스트를 생성합니다. n+1개인 이유는 1번 컴퓨터를 1번 인덱스를 쓰기 위해, 1개 더 추가한 것입니다. visited는 n+1 길이의 0으로 이루어진 리스트로, 해당 컴퓨터를 방문했는지 표시하는 리스트입니다.(0: 미방문, 1: 방문)

연결선 개수만큼 for문을 반복하며 연결된 컴퓨터 번호를 각각 a, b로 입력받습니다. graph에서 a컴퓨터에 b를 넣고, b컴퓨터에 a를 넣음으로써 쌍방 연결돼있음을 표시합니다.

컴퓨터간 연결 시각화

위 예제에 대한 그래프는 아래와 같은 이중 리스트로 표현됩니다. 0번 컴퓨터는 없으니, 맨 앞에는 빈 리스트입니다. 1번 컴퓨터는 2번과 5번에 연결되어 있으니 [2, 5]를 값으로 같습니다. 이렇게 인덱스가 컴퓨터 번호이고, 값이 연결된 컴퓨터의 리스트인 이중 리스트입니다.

graph 이중 리스트

여기까지가 공통부분이고, 이제 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 두 가지 모두를 이용해 문제를 풀어보겠습니다.

 

* 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색과 너비 우선 탐색

 

2) BFS 알고리즘

from collections import deque
visited[1]=1 # 1번 컴퓨터부터 시작이니 방문 표시
Q=deque([1])
while Q:
    c=Q.popleft()
    for nx in graph[c]:
        if visited[nx]==0:
            Q.append(nx)
            visited[nx]=1
print(sum(visited)-1)

BFS는 deque를 사용합니다. visited[1]=1 로 첫 번째 컴퓨터에 방문 표시를 합니다. Q=deque([1]) 로, 첫 번째 컴퓨터에 대해 덱을 만듭니다. Q에 값이 있는 동안 while문을 돌며, c=Q.popleft()를 통해 Q에서 맨 왼쪽에 있는 값이 지워지며, c에 들어갑니다. c는 current의 약자로 현재 컴퓨터를 의미합니다. 다음으로 g[c]는 c컴퓨터와 연결된 컴퓨터들의 리스트로 이를 nx(next)로 반복합니다. nx 컴퓨터가 방문되지 않은 컴퓨터라면, visited[nx]==0가 참이 됩니다. 그러면, Q에 추가되고, visited[nx]=1로 방문 표시를 합니다. while문이 반복되다 보면 1번 컴퓨터와 연결된 모든 컴퓨터들이 visited에서 1로 방문 표시됩니다. 마지막에 sum(visited)를 하면 1번 컴퓨터를 포함해 방문 표시된 컴퓨터들의 개수가 나옵니다. sum(visited) - 1을 해서, 1번 컴퓨터를 제외하고 출력해줍니다.

(그럼 굳이 처음에 visited[1]=1을 안 하고, 마지막에 sum(visited)-1 대신 sum(visited)를 출력하면 되는 거 아닌가?라는 의문이 있을 수 있습니다. 하지만 1번 컴퓨터와 연결된 컴퓨터에서 방문하지 않은 컴퓨터를 모두 방문하니 1번 컴퓨터가 다시 방문될 것입니다. 그러면 처음에 visited[1]=1을 안 해도 1번 컴퓨터에 연결된 컴퓨터가 있다면, 연결은 쌍방향이니, 해당 컴퓨터 방문하고 다시 1번 컴퓨터 방문하겠네요라고 할 수 있습니다. 생각해보니 이건 맞습니다. 위 코드에서 visited[1]=1을 제외하고 제출했는데 백준에서 정답 판정을 받았습니다. 블로그를 쓰지 않았다면 발견하지 못했을 히든 포인트였습니다.)

 

3) DFS 알고리즘

def dfs(v):
    visited[v]=1
    for nx in graph[v]:
        if visited[nx]==0:
            dfs(nx)
dfs(1)
print(sum(visited)-1)

DFS는 훨씬 간단합니다. dfs 함수는 방문할 컴퓨터 번호를 v로 입력받습니다. 바로 visited[v]=1로 방문 표시를 하고, graph[v]는 v번 컴퓨터에 연결된 컴퓨터들의 리스트입니다. 각 컴퓨터를 nx(next)로 반복하며, visited[nx]==0을 통해 해당 컴퓨터가 방문되지 않은 컴퓨터인지 검사합니다. 방문되지 않았다면, dfs(nx) 재귀 호출을 통해 해당 컴퓨터를 방문하고 이 과정을 반복합니다. 그렇게 되면, 1번 컴퓨터부터 방문하고 연결된 컴퓨터들을 재귀 호출을 하며 쭈르륵 방문합니다. 여기서 dfs함수에 visited를 인자로 입력받지도 않고, return하지도 않았는데 어떻게 print(sum(visited)-1)이 정답이 될 수 있는지 궁금할 수 있습니다. visited는 리스트로 파이썬의 리스트는 함수 밖에서 선언되어, 함수 내부에서 변경되어도, 함수 밖에서 변경이 적용됩니다. 즉, dfs함수 내부에서 변경된 visited 리스트는 함수 밖에서도 변경이 적용되기 때문에, sum(visited) - 1이 정답이 될 수 있습니다. -1 한 이유는 1번 컴퓨터를 제외하고, 1번 컴퓨터와 연결된 컴퓨터 개수를 출력해야 하기 때문입니다.

 

4. 느낀 점

위처럼 1번 컴퓨터와 연결된 컴퓨터들을 찾는 문제를 연결 요소 찾기 문제라고 합니다. 연결 요소란 그래프 상에서 이어져 있는 모든 요소들이 있을 때, 그것을 싸잡아 하나의 연결 요소라고 합니다. DFS와 BFS 둘 다로 풀 수 있는 적당한 난이도의 문제로, 그래프 탐색 연습하기 좋은 문제 같습니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

Reference)
1. DFS와 BFS: https://velog.io/@xmun74/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS