[프로그래머스] 네트워크 (Swift)

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

코딩테스트 연습 - 네트워크

DFS (깊이 우선 탐색)

n개의 컴퓨터들이 서로 연결되어 있는 상태 정보를 2차원 배열로 알려주고

n개의 컴퓨터들이 구성하는 네트워크가 몇개인지 구하는 문제

 

접근방법

dfs로 풀지 bfs로 풀지 고민하다가 아무래도 dfs로 푸는게 맞는 것 같아서 dfs로 풀었다.

 

2차원 배열을 모두 보면서 서로 연결된 컴퓨터들을 확인할 것인데

네트워크 하나가 끝나는 지점을 어떻게 알것이며 그때 네트워크 개수를 어떻게 증가시킬건지 고민했다.

 

결론은 dfs로 깊이 들어가다가 마지막에 네트워크 개수를 증가시키는게 아니라 처음 시작할 때 네트워크를 1 증가시키고

더이상 방문할(연결된) 컴퓨터가 없을 때에는 그냥 재귀 dfs함수를 종료시키는 것으로 풀이했다.

이때 dfs함수의 역할은 현재 위치한 컴퓨터로부터 연결된 다른 컴퓨터들을 방문하면서 컴퓨터별 방문여부를 갱신해주는 것이다. ( = 방문했으면 visits 배열의 해당 컴퓨터 인덱스를 true로 변환)

 

1. solution 함수에서 !방문하지 않은! 모든 컴퓨터를 시작점으로 하는 dfs 함수를 호출한다. 호출과 동시에 네트워크 개수(numOfNetwork)를 1증가시킨다. = 해당 컴퓨터가 포함된 네트워크가 1개 존재한다는 것

2. dfs함수 실행

    2-1. dfs 함수 내부에서는 현재 컴퓨터 인덱스를 받아서 해당 컴퓨터를 방문했다고 표시한다.

    2-2. computers 배열의 현재 컴퓨터 인덱스 행 하나(현재 컴퓨터와 다른 컴퓨터들의 연결 여부)를 순회하면서, 연결되어 있고 (값이 1) && 아직 방문하지 않은 컴퓨터이면 -> 그 컴퓨터를 인자에 담아 dfs함수를 호출한다.

   *더이상 새로 방문할 컴퓨터가 없을때 dfs함수는 종료

 

최대 네트워크 수는 모든 컴퓨터가 독립적일때 즉, 연결되어있지 않을 때이며. 이때 네트워크 수는 n(컴퓨터 수)이다.

그렇기 때문에 solution함수에서 모든 컴퓨터를 확인하면서, 아직 방문하지 않은 컴퓨터라면 그 이전의 컴퓨터들이 구성하는 네트워크에 포함되지 않은 컴퓨터라는 의미이므로 해당 컴퓨터에서부터 dfs 함수를 실행하는 것이다.

 

**

함수 안에 함수를 사용하지 않았었는데 이번에 풀이한 후에 다른분 코드를 보고 고쳐봤다.

전역에서 사용할 배열이나 변수가 있을 경우에 사용하면 편리할 것 같다.

 

소스코드

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var visits = Array(repeating: false, count: n)
    var numOfNetwork:Int = 0
    
    func dfs(_ com:Int) {
        visits[com] = true
        for i in 0..<n {
            if computers[com][i] == 1 && !visits[i] {
                dfs(i)
            }
        }
    }
    
    for i in 0..<n {
        if !visits[i] {
            numOfNetwork += 1
            dfs(i)
        }
    }
    
    return numOfNetwork
}