용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (250)
    • 개발 (77)
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (21)
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

[프로그래머스 Lv.3] 네트워크 (Python)
알고리즘/알고리즘 문제 풀이

[프로그래머스 Lv.3] 네트워크 (Python)

2024. 3. 30. 10:42

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

deque를 사용한 BFS로 문제를 풀이하였다. 일반적인 BFS 문제를 풀이하는 것처럼 visited라는 배열을 통해 네트워크를 구성할 노드의 방문 여부를 확인하여 전체 노드 순회를 완료하였을 때 몇 개의 네트워크를 생성할 수 있는지 확인하면 된다. 

from collections import deque
def solution(n, computers):
    answer = 0
    
    visited = [0 for _ in range(n)] # 각 노드의 방문 여부를 저장할 배열
    
    d = deque() # BFS를 위한 덱 자료구조
    
    for i in range(n): # 노드 전체를 순회하면서
        if visited[i] == 1: # 이미 방문한 노드는 스킵
            continue
        
        d.append(i) # 방문 안한 노드를 BFS를 위해 덱에 저장
        answer += 1 # 새로운 노드에서 BFS를 시작했다는 것은 새로운 네트워크를 순회하기 시작했다는 것이므로 갯수 증가
        
        while len(d) > 0: # 덱이 빌 때까지
            cur = d.popleft() # 현재 노드

            visited[cur] = 1 # 현재 노드 방문 표시

            for i in range(n): # 현재 노드와 연결된 모든 노드들을 체크
                if cur != i and visited[i] == 0 and computers[cur][i]: # 체크하는 노드가 자기 자신이 아니고, 이미 방문한 노드가 아니고, 연결된 노드인지 확인
                    d.append(i) # 덱에 저장
        
    return answer

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

[프로그래머스 Lv.3] 풍선 터트리기 (Python)  (0) 2024.04.06
[프로그래머스 Lv.3] 이중우선순위큐 (Python)  (0) 2024.04.02
[프로그래머스 Lv.3] 정수 삼각형 (Python)  (0) 2024.03.27
[프로그래머스 Lv.3] 최적의 행렬 곱셈 (Python)  (0) 2024.03.26
(Python) 백준 1912번 - 연속합  (0) 2024.03.22
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • [프로그래머스 Lv.3] 풍선 터트리기 (Python)
    • [프로그래머스 Lv.3] 이중우선순위큐 (Python)
    • [프로그래머스 Lv.3] 정수 삼각형 (Python)
    • [프로그래머스 Lv.3] 최적의 행렬 곱셈 (Python)
    용꿀
    용꿀

    티스토리툴바