문제 링크
문제 요약
BFS/DFS 문제 유형에 해당한다.문제에서 네트워크는 컴퓨터들이 정보를 교환할 수 있도록 연결된 형태를 의미함. 예를 들어, 컴퓨터 A와 B가 연결되고, B와 C가 연결되면, A와 C는 간접적으로 연결된 것을 의미 함. 주어진 컴퓨터의 개수(n)와 각 컴퓨터 간의 연결 정보(computers 2차원 배열)를 바탕으로 네트워크의 총 개수를 반환하는 함수를 작성!
문제 풀이
def DFS(computer_num, computers, visited, n):
visited[computer_num] = 1 # 해당 컴퓨터 방문처리
for i in range(n):
if computers[computer_num][i] == 1 and not visited[i]:
DFS(i, computers, visited, n)
# 연결되면 하나의 네트워크
def solution(n, computers):
ans = 0
visited = [0] *n # DFS에서 사용할 방문 체크
# DFS의 시작점이 딱히 정해져 있지 않다... !
for i in range(n):
if not visited[i]:
DFS(i, computers, visited, n)
ans +=1
return ans
📌 고려해야할 점
- 각 컴퓨터가 얼마나 많은 컴퓨터와 연결되었는지 확인하는 것이기 때문에
DFS로 접근 - 다만, 기존에 많이 풀던 DFS와는 다르게 시작점이 딱히 정해져있지 않다! 따라서, 컴퓨터 개수에 따라 for문을 돌면서 인덱스가 컴퓨터의 라벨이라고 생각하고 DFS에 보내주기!
- DFS에 들어가서 최대한으로 연결하고 연결된 컴퓨터 라벨을 방문한 것으로 처리해주고 돌아오면 그 때가
네트워크 1개형성한 것!
