알고리즘 - 네트워크 (DFS, BFS) 프로그래머스

hee·2022년 12월 7일
0

알고리즘

목록 보기
8/10

네트워크 (DFS, BFS) 프로그래머스

DFS, BFS 문제 풀이에 익숙해지기 위해 두 방법으로 문제를 해결해볼려고 노력 중 입니다.
이 문제는 프로그래머스에 DFS, BFS 관련 문제로 문제 제목은 네트워크 입니다.
컴퓨터의 개수 n, 연결 정보 computers 2차원 리스트를 받아 연결된 네트워크의 개수를 반환하는 문제 입니다. 컴퓨터간의 네트워크가 직접적으로든 간접적으로든 연결되어 있다면 그것은 하나의 네트워크를 사용하고 있다고 볼 수 있습니다.
먼저 DFS로 문제를 해결해 봤습니다.

def solution(n, computers):
    answer = 0
    visited = [False]*n # 방문처리 리스트를 만들기 
    def dfs(i):
        visited[i] = True # 방문처리 
        for l in range(n):
            if computers[i][l] and not visited[l]: # 연결 정보에 연결되어 있고 아직 방문처리가 되지 않았다면 dfs(i)를 호출하여 방문처리 
                dfs(l)

    for i in range(n): # 0 인덱스부터 for문 돌리기
        if visited[i] == False: # 방문처리 리스트에서 해당 인덱스가 False라면 아직 미방문이라면 dfs(i) 호출해서 방문처리
            dfs(i)
            answer+=1 # 더이상 연결정보에 방문할 컴퓨터가 없다면 하나의 네트워크가 만들어진 것이기 때문에 +1
    return answer

위의 코드는 DFS 문제를 해결한 코드 입니다. dfs(i)를 만들어 방문하지 않았고 연결정보에 연결되어 있다면 방문처리를 하는 기능을 만듭니다. 더이상 연결정보에 방문할 컴퓨터가 없다면 dfs(i)가 종료되고 하나의 네트워크가 만들어진것이기 때문에 +1을 하며 네트워크의 개수를 기록라는 코드 입니다.

BFS로 문제를 해결해본 코드 입니다.

from collections import deque
def solution(n, computers):
   answer = 0
   queue = deque()
   visited = [False]*n

   for i in range(n):
       if visited[i] == False: # 방문처리 되어있지 않다면 
           visited[i] = True # 방문처리 
           answer+=1 # 네트워크의 개수 +1
           queue.append(i) # 방문처리한 인덱스 append
       while queue:
           i = queue.popleft()  # 방문처리한 인덱스 꺼내기 
           for l in range(n):
               if computers[i][l] and not visited[l]:
                   visited[l] = True # 방문처리되지 않은 인덱스 방문처리
                   queue.append(l) # 방문처리한 인덱스 append
   return answer

위의 코드는 queue를 이용한 넒이 우선탐색으로 해결한 코드 입니다.

0개의 댓글

관련 채용 정보