[프로그래머스] Lv.3 네트워크

Python3, DFS/BFS

문제

제한 사항

입출력 예시

나의 풀이 (시도)

• computer i, j가 연결되어 있으면 computers[i][j]는 1이다
• computers[i][i] 는 1이다

def solution(n, computers):
    answer = 0
    
    for i in computers:
        for j in computers:
            if computers[i] == computers[j]:
                computers[i][j] = 1
            computers[i][i] = 1
    return answer

주요 포인트

dfs 로 구현

모든 컴퓨터를 다 돌 때까지 dfs 반복한다
visited라는 빈 배열을 [False, False, False..] 로 초기화를 시키고 직/간접적으로 방문할 때마다 True로 바꾼다
아직 방문하지 않은 컴퓨터가 있으면 answer 값을 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 가장 작은 번호부터 dfs 다시 호출한다
모든 컴퓨터를 방문하면 반복문을 종료하고, answer 값을 반환한다

최종 코드

def dfs(n, computers, start, visited):
    visited[start] = True
    for i in range(0, n):
        if(visited[i] == False and computers[start][i] == 1):
            visited = dfs(n, computers, i, visited)
               
    return visited

def solution(n, computers):
    answer = 0
    # 빈 배열에 False를 n개 만큼 채워 넣기
    visited = [False] * n
    
    for start in range(0, n):
        if(visited[start] == False):
            dfs(n, computers, start, visited)
            answer += 1
            
    return answer

아직은 어렵다.. 하다 보면 발전하겠지..
중요한 내용이니 다시 한 번 더 꼼꼼하게 살펴 보자