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

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

기본적인 DFS로 풀이가능한 문제입니다.

이 문제도 기본유형의 문제라 레벨이 높은 상태인것 같습니다.

아직 탐색하지 않은 computer를 만나면 DFS로 연결된 모든 컴퓨터들을 탐색하고, 방문처리해주면 됩니다.

DFS 한번에 연결된 컴퓨터들이 전부 방문되기 때문에 정답인 네트워크의 갯수는 DFS의 호출횟수와 같습니다.

 

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            findNetwork(i, computers, visited)
            answer += 1

    return answer


def findNetwork(now, computers, visited):
    for next in range(len(computers[now])):
        if computers[now][next] == 1 and not visited[next]:
            visited[next] = True
            findNetwork(next, computers, visited)
            


print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))