내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
네트워크
ps:problems:programmers:43162
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 네트워크 ====== ===== 풀이 ===== * 커넥티드 컴포넌트의 갯수를 찾는 문제. * 특정 노드와 연결된 노드를 모두 찾는 것은 BFS와 DFS중 어느 방법으로든 가능하지만, 여기서는 DFS를 사용. * 커넥티드 컴포넌트의 갯수에 관계 없이, 모든 노드를 1번씩 방문하게 되므로, 시간 복잡도는 O(V+E)이다. 여기에서는 E = O(V^2) 이므로 전체 시간복잡도도 O(V^2)이다. ===== 코드 ===== <dkpr py> """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 </dkpr> * Dependency: [[:ps:teflib:search#simple_dfs|teflib.search.simple_dfs]] {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/43162.txt
· 마지막으로 수정됨: 2021/06/30 15:38 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로