프로그래머스 Lv. 3 Swift 알고리즘 - 네트워크_DFS

간만에 프로그래머스 문제를 푸는것 같다... 그 동안 백준 문제를 풀었는데 프로그래머스가 확실히 백준보다 좀 쉬운거 같기도..?

하지만 이번 문제는 실제 난이도에 비해 푸는데 오래 걸리긴 했다 😇

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 네트워크가 연결되어 있으면 연결된 개체를 전부 묶어서 Count + 1 이다.
2. 그렇다면 연결이 끊어질때까지 이어보자 -> DFS
3. 항상 그렇듯이 vistied 배열을 만들어준다. 이때 우리는 n개의 컴퓨터의 각각 상황만 파악하면 되기 때문에
4. vistied를 2차원 배열이 아닌 1차원 배열로 만들어준다.
5. A부터 시작하면 어디까지 연결될까? Try...
6. B부터 시작하면 어디까지 연결될까? Try...
7. 이렇게 반복인데 이때 A에서 시작했을 경우 B와 연결이 되어있었다면 이미 visited 배열엔 B의 자리에 True 값이 들어있을 것이다.
8. 그래서 이렇게 미리 count를 1 올려주고 dfs의 재귀가 끝날때까지 돌려준다.
9. 이렇게 모든 위치를 방문했다면 끝.

 

 

* 코드

import Foundation

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

 

 

정리(Today I Learned)

1. 문제가 처음 주어질때 대칭형태로 배열이 나오는 것을 보고 이걸 어떻게 해결해야 할까... 고민을 많이했다. 뭔가 경로를 쉽게 파악할 수 있는 논리가 숨겨져 있을것 같기도하고 해서... 근데 결국 단순하게 생각하는게 답이었던 것 같다. DFS로 풀 수 있겠다는 생각이 든다면 값의 끝을 볼 수 있는 경로를 어떻게 설계할지 고민해보면 좋을 것 같다.