프로그래머스 [lv3] 네트워크 파이썬
접근
-
주어진 것을 정리 : 노드(컴퓨터)의 갯수, 비방향성, 연결선
-
첫 시도: key(컴퓨터) - value (key와 연결된 컴퓨터) 구조의 dictionary 작성 시도
-> 못품 ㅎ ㅠ -
dfs로 접근 : 이미 방문한 노드를 체크하기 위해 visited 리스트 생성
-> 원소는 모두 0으로 채우고, while문으로 0이 나오지 않을 때 까지 체크 -
현재 방문중인 노드(컴퓨터)와 연결된 컴퓨터를 모두 찾기 위해 dfs 스택 선언
-
dfs 스택에 append될 조건은, 아직 방문하지 않은(visited[i]==0) 동시에(and) 현재 방문중인 노드와 연결 돼(computers[curr][i]) 있을 때
풀이 1) 반복문 사용
def solution(n, computers):
visited = [0] * n
result = 0
dfs = list()
while 0 in visited:
dfs.append(visited.index(0))
while dfs:
curr = dfs.pop()
visited[curr] = 1
for i in range(n):
if computers[curr][i] == 1 and visited[i] == 0:
dfs.append(i)
result += 1
return result
풀이 2) 재귀문 사용
def solution(n, computers):
answer = 0
visited = [0] * n
def dfs(computers, visited, start):
stack = [start]
while stack:
j = stack.pop()
visited[j] = 1
for i in range(0, len(computers)):
if computers[j][i] ==1 and visited[i] == 0:
stack.append(i)
return
i=0
while 0 in visited:
if visited[i] ==0:
dfs(computers, visited, i)
answer +=1
i+=1
return answer
아쉬운 점 및 정리
- 풀이 1번 : 이중 while 문 구성 -> 시간복잡도 O(n^2)
- 실행 속도는 풀이 1번이 조금 더 빠르다. (반복문이 재귀보다 빠르다)
Author And Source
이 문제에 관하여(프로그래머스 [lv3] 네트워크 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tbnsok40/프로그래머스-lv3-네트워크-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)