문제
https://school.programmers.co.kr/learn/courses/30/lessons/43162
- 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
- 쉽게 말하면, 네트워크는 서로 연결되지 않은 독립적인 노드 그룹의 개수이다.
예제 1)
아래 그림의 경우 총 2개의 네트워크가 존재한다.
예제 2)
아래의 경우 총 1개의 네트워크가 존재한다.
- 입출력 예
풀이
1번 노드부터 각 노드에서 연결되어 있는 모든 노드를 최대한 탐색한 후, 더 이상 연결된 노드가 없으면 탐색을 종료한다. 탐색을 종료하면 answer의 값을 1 증가시킨 후, 다음 노드에 연결된 노드들을 모두 탐색하는 동일한 과정을 진행한다. 더 이상 탐색할 노드가 없으면 알고리즘을 종료한 후 정답을 return 한다.
코드
- 처음 문제를 보고 생각했을 때는 DFS만 활용해서 풀 수 있는 문제라고 생각했다. 다른 사람들의 풀이를 참고해보니 해당 문제는 DFS 뿐만 아니라 BFS로도 풀이할 수 있었다.
- 두 가지 방법을 모두 사용해서 문제를 풀어보고자 한다.
DFS 코드
def solution(n, computers):
answer = 0
visited = [False for _ in range(n)] # 방문 여부 저장 배열
for com in range(n):
if visited[com] == False: # 1번 ~ n번 컴퓨터까지 가면서 방문하지 않은 컴퓨터라면
DFS(n, computers, com, visited)
answer += 1
return answer
def DFS(n, computers, com, visited):
visited[com] = True # 해당 노드의 방문 여부를 True로 변경
for i in range(n): # 해당 노드와 연결된 다음 노드들을 모두 탐색
if i != com and computers[i][com] == 1 and visited[i] == False:
DFS(n, computers, i, visited) # i랑 연결된 다음 노드도 쭉 탐색
# 자기 자신이 아니고, 이전 노드(com)와 현재 노드(i)가 연결된 노드이며, 현재 노드가 방문하지 않은 노드라면 방문하고, 현재 노드(i)에 대한 DFS를 계속 진행
# 연결되지 않은 노드가 나오는 순간 DFS 종료BFS 코드
1)
from collections import deque
def solution(n, computers):
answer = 0
visited = [False for _ in range(n)]
for com in range(n):
if visited[com] == False:
BFS(n, computers, com, visited)
answer += 1
return answer
def BFS(n, computers, com, visited):
visited[com] = True # 방문을 했으므로 방문여부를 참으로 변경
queue = deque()
queue.append(com)
while len(queue) > 0: # 큐에 요소가 남아있는 동안 계속 append, pop 작업을 진행
com = queue.pop()
visited[com] = True
for i in range(n):
if visited[i] == False and computers[i][com] == 1 and i!=com:
queue.append(i)2) BFS 방식으로 풀이하였는데, BFS 내부 자체에서 재귀를 사용했다. 아래 방식보다는 위의 BFS 또는 DFS 방식으로 구현하면 좋을 것 같다.
from collections import deque
def solution(n, computers):
answer = 0
visited = [False for _ in range(n)]
for com in range(n):
if visited[com] == False:
BFS(n, computers, com, visited)
answer += 1
return answer
def BFS(n, computers, com, visited):
visited[com] = True # 방문을 했으므로 방문여부를 참으로 변경
queue = deque()
queue.append(com)
for i in range(n):
if visited[i] == False and computers[i][com] == 1 and i!=com:
BFS(n, computers, i, visited)
👩🏻💻 AI를 좋아하는 IT학부생