사용자 도구

사이트 도구


ps:problems:programmers:43162

네트워크

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호43162
문제명네트워크
레벨Level 3
분류

DFS

시간복잡도O(V^2)
인풋사이즈V<=200
사용한 언어Python
해결날짜2021/06/30
태그

고득점 Kit - DFS/BFS

풀이

  • 커넥티드 컴포넌트의 갯수를 찾는 문제.
  • 특정 노드와 연결된 노드를 모두 찾는 것은 BFS와 DFS중 어느 방법으로든 가능하지만, 여기서는 DFS를 사용.
  • 커넥티드 컴포넌트의 갯수에 관계 없이, 모든 노드를 1번씩 방문하게 되므로, 시간 복잡도는 O(V+E)이다. 여기에서는 E = O(V^2) 이므로 전체 시간복잡도도 O(V^2)이다.

코드

"""Solution code for "Programmers 43162. 네트워크".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43162
- Solution link: http://www.teferi.net/ps/problems/programmers/43162
"""

from teflib import search


def solution(n, computers):
    def next_states(u):
        return (v for v, is_connected in enumerate(computers[u])
                if is_connected == 1)

    is_visited = [False] * n
    answer = 0
    for u in range(n):
        if is_visited[u]:
            continue
        for node in search.simple_dfs(next_states, u):
            is_visited[node] = True
        answer += 1
    return answer

토론

댓글을 입력하세요:
X D D Y J
 
ps/problems/programmers/43162.txt · 마지막으로 수정됨: 2021/06/30 15:38 저자 teferi