민규의 흔적

[Python 파이썬] 프로그래머스 - 네트워크 본문

프로그래머스

[Python 파이썬] 프로그래머스 - 네트워크

민규링 2024. 8. 6. 01:29

2024년 8월 6일

문제 링크 : 프로그래머스 - 네트워크


문제 접근

 

문제 자체는 엄청 간단하다.

 

서로 이어져있는 여러 대의 컴퓨터가 존재할 때, 각 컴퓨터끼리 이루는 네트워크의 총 개수를 구하면 되는 문제이다.

 

모든 컴퓨터를 하나씩 시작점으로 지정해보며 만약 아직까지 어느 네트워크에도 소속되지 않은 컴퓨터라면, 해당 컴퓨터를 시작점으로 BFS 로직을 수행해 같은 네트워크에 존재하는 모든 컴퓨터를 알아내기를 반복하면 된다.

 

BFS 로직을 수행한 횟수가 곧 총 네트워크의 개수가 된다.

 


전체 코드

 

from collections import deque

def solution(n, computers):
    answer = 0

    visited = [False] * n

    for start_v in range(n):
        if visited[start_v]:
            continue
        queue = deque()
        queue.append(start_v)
        visited[start_v] = True

        while queue:
            now_v = queue.popleft()
            for next_v in range(n):
                if next_v == start_v:
                    continue
                if computers[now_v][next_v] == 1 and not visited[next_v]:
                    queue.append(next_v)
                    visited[next_v] = True

        answer += 1

    return answer

if __name__ == "__main__":
    print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

풀이 후기

 

BFS로 풀 수 있는 간단한 문제였다.