주제 - “알고리즘 (DFS/BFS) - 2”
부제 - 프로그래머스 코딩테스트 연습 - 파이썬
출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 네트워크
- 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.
문제 2. 네트워크
[문제 설명]
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
[제한사항]
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터
n-1인 정수로 표현합니다. - i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면
computers[i][j]를 1로 표현합니다. computer[i][i]는 항상 1입니다.
[입출력 예]
| n | computers | return |
|---|---|---|
| 3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
| 3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
풀이
def solution(n, computers):
answer = 0
bfs = []
visited = [0]*n
while 0 in visited:
bfs.append(visited.index(0))
while bfs:
node = bfs.pop(0)
visited[node] = 1
for i in range(n):
if visited[i] == 0 and computers[node][i] == 1:
bfs.append(i)
answer += 1
return answer
풀이의 포인트
각 컴퓨터끼리의 연결 여부를 파악하여 네트워크의 개수를 파악하는 문제입니다.
아래의 그림과 같이 선으로 연결된 모든 컴퓨터들은 하나의 네트워크를 구성하는 것입니다.
네트워크의 개수를 파악하기 위해, 하나의 네트워크를 구성하는 컴퓨터들을 확인할 필요가 있습니다. 하나의 컴퓨터에 연결된 컴퓨터들을 체크하여 네트워크 구성을 파악해보겠습니다.
1) 문제 파악하기 : BFS
컴퓨터들은 연결만 되어있으면 네트워크를 구성하므로, 깊이를 파악할 필요는 없습니다. 연결된 컴퓨터들을 따라 탐색해야 하므로 BFS를 사용하여 네트워크를 파악합니다.
특히 네트워크의 총 개수를 파악하는 것이 목적이므로, 하나의 네트워크 파악이 완료되면 다른 네트워크를 구성하는 컴퓨터들을 이어서 확인해야 합니다.
2) BFS 구현하기 (큐)
BFS 구현에는 흔히 큐를 사용합니다. 노드를 큐에 넣고, 하나씩 꺼내면서 인접한 노드들을 탐색하기 때문입니다. 큐를 이용하여 BFS를 구현하는 기본적인 형태는 아래와 같습니다.
- 탐색을 위한 큐, 방문한 노드를 체크해 둘 리스트 생성
- 탐색을 시작할 노드를 큐에 넣기 (탐색 시작 노드의 방문 표시 해두기)
- 큐가 빌 때까지 반복문 수행
- 큐의 앞에서부터 노드를 하나씩 꺼내기
- 꺼낸 노드에 인접한 노드들을 방문하는 반복문 수행
- 방문한 노드가 이전에 방문한 적이 없다면 큐에 넣기
- 방문한 노드는 체크해두기
위 형태를 적용하여 코드 작성을 시작합니다.
(1) 먼저, 탐색을 위한 큐, 방문한 노드를 체크해 둘 리스트, 네트워크의 개수를 저장할 변수를 생성합니다.
(2) 탐색을 시작할 첫 노드를 큐에 넣습니다. 큐에 들어가는 값은 인덱스로, 이 문제에서는 computers 리스트의 첫번째 인덱스를 큐에 넣는 것으로 시작합니다. 그리고 첫 노드를 방문했음을 표시합니다.
(3) 큐가 빌 때까지 반복문을 아래 내용을 반복으로 수행합니다.
(3-1) 큐의 앞에서부터 노드를 하나씩 꺼냅니다.
(3-2) 꺼낸 노드의 인접 노드들을 방문하는 반복문을 수행합니다.
(3-2-1) 인접 노드가 방문된 적이 없다면 큐에 넣고, 방문했음을 표시합니다.
def solution(n, computers):
# 1
answer = 0 # 네트워크의 개수를 저장할 변수
bfs = [] # 탐색을 위한 큐
visited = [0]*n # 방문한 노드를 체크해 둘 리스트
#2
bfs.append(0) # 큐에 첫 노드(인덱스) 추가
visited[0] = 1 # 첫 노드 방문 표시
#3
while bfs: # 큐가 값이 존재하면 반복문 수행
# 3-1
node = bfs.pop(0) # 큐의 앞에서부터 노드(인덱스) 꺼내기
# 3-2
for i in range(n): # 꺼낸 노드의 인접 노드를 방문하기 위한 반복문 수행
# 3-2-1
if visited[i] ==0 and computers[node][i] == 1: # 인접 노드이고, 방문된 적이 없는 경우
bfs.append(i) # 큐에 추가
visited[i] = 1 # 방문했음을 표시
위의 형태까지 코드를 구성하면, 첫 노드와 연결된 노드들로 구성된 하나의 네트워크만을 탐색합니다.
하지만 문제의 목표는 모든 네트워크의 개수이므로, visited 리스트의 모든 값에 방문표시가 되어있을 때까지 반복을 수행해야 합니다.
def solution(n, computers):
answer = 0
bfs = []
visited = [0]*n
while 0 in visited: # visited 리스트의 모든 값에 방문 표시가 되어있을 때까지 반복
bfs.append(0)
visited[0] = 1
while bfs:
node = bfs.pop(0)
for i in range(n):
if visited[i] == 0 and computers[node][i] == 1:
bfs.append(i)
visited[i] = 1
answer += 1 # 한 네트워크의 탐색을 마치면 개수 추가
return answer
위와 같이 while 0 in visited 반복문을 추가해주면, 탐색 시작 노드를 추가하는 부분인 bfs.append(0) 때문에 같은 노드를 반복하여 탐색하게 됩니다. 그렇기에 이 부분의 수정이 필요합니다.
이 부분은 탐색을 위해 큐에 노드를 추가하는 것이므로, 직접 인덱스를 넣는 것이 아니라 방문하지 않은 노드를 추가하는 것으로 수정합니다. 방문하지 않은 노드를 visited.index(0)로 찾아내서 사용합니다.
따라서 최종적으로 아래와 같은 코드가 완성됩니다.
def solution(n, computers):
answer = 0
bfs = []
visited = [0]*n
while 0 in visited:
x = visited.index(0)
bfs.append(x)
visited[x] = 1
while bfs:
node = bfs.pop(0)
visited[node] = 1
for i in range(n):
if visited[i] == 0 and computers[node][i] == 1:
bfs.append(i)
visited[i] = 1
answer += 1
return answer
또는, 노드의 방문을 표시하는 부분을 아예 큐에서 꺼낸 직후에 하는 방법도 있습니다. 그렇다면 아래와 같은 코드가 완성될 수 있습니다.
(이 방법은 위의 방법보다 반복문 수행횟수가 많습니다.)
def solution(n, computers):
answer = 0
bfs = []
visited = [0]*n
while 0 in visited:
bfs.append(visited.index(0))
while bfs:
node = bfs.pop(0)
visited[node] = 1
for i in range(n):
if visited[i] == 0 and computers[node][i] == 1:
bfs.append(i)
answer += 1
return answer