네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
나의 풀이
오랜만에 BFS/DFS문제를 풀어보았다. 아무래도 오랜만에 푸는만큼 같은문제를 두가지 방법으로 풀어보는게 좋을 것같아서 그렇게 했다.
DFS
DFS같은경우 방문하지않았다면 DFS를 돌려서 방문처리를 해준다. 그런다음 방문처리하지 않은 컴퓨터를 찾으면 새로운 네트워크로 갯수를 세어주는 식이다.
def solution(n, computers):
def DFS(i):
visited[i] = 1
for a in range(n):
if computers[i][a] and not visited[a]:
DFS(a)
answer = 0
visited = [0 for i in range(len(computers))]
for i in range(n):
if not visited[i]:
DFS(i)
answer += 1
return answer
BFS
BFS같은경우 비슷한 로직이다. 하지만 BFS는 재귀가 아니라 q스택을 활용하여 넓이 우선탐색이 다른 점이다.
from collections import deque
def solution(n, computers):
def BFS(i):
q = deque()
q.append(i)
while q:
i = q.popleft()
visited[i] = 1
for a in range(n):
if computers[i][a] and not visited[a]:
q.append(a)
answer = 0
visited = [0 for i in range(len(computers))]
for i in range(n):
if not visited[i]:
BFS(i)
answer += 1
return answer
후기
bfs는 항상 금방 구현하는데 dfs는 조금 생각하게 되는거같다.
dfs도 금방 구현할 수 있도록 익혀두자
그리고 보통 bfs가 dfs보다 빠른데 이번 코드를 보면 딱히 그런것같지도 않고 시간이 적을수록 bfs가 빠르고 시간이 많이 들수록 dfs가 빠르다.
왜인지 생각해보는걸 과제로 남겨야겠다.
성장스택 쌓고있는 개발자🏋