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

 

 

접근

1. 주어진 것을 정리 : 노드(컴퓨터)의 갯수, 비방향성, 연결선

2. 첫 시도: key(컴퓨터) - value (key와 연결된 컴퓨터) 구조의 dictionary 작성 시도 -> 못품 ㅎ ㅠ

3. dfs로 접근 : 이미 방문한 노드를 체크하기 위해 visited 리스트 생성
-> 원소는 모두 0으로 채우고, while문으로 0이 나오지 않을 때 까지 체크

4. 현재 방문중인 노드(컴퓨터)와 연결된 컴퓨터를 **모두** 찾기 위해 dfs 스택 선언

5. 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. 풀이 1번 : 이중 while 문 구성 -> 시간복잡도 O(n^2)
2. 실행 속도는 풀이 1번이 조금 더 빠르다. (반복문이 재귀보다 빠르다)