[Swift] [90일차] 네트워크_programmers

네트워크

---

문제 설명

1. 네트워크라고 주장하는 간선 노드가 등장
2. 배열 형태를 보고 연결된 것끼리 하나의 네트워크라고 가정했을 때 총 네트워크의 개수를 구하라
3. 단순히말해서 뭉쳐진애는 1개로 카운팅해서 총 개수 구하라

---

문제 풀이

1. 나눠져있는 섬의 개수를 구하는 문제라고 볼 수 있어서, dfs를 사용해주기로했다.
2. 0..<n까지 순회하면서 출발을하는데, 방문배열을 해당 반복문에서 뚫을때(F -> T)마다 카운팅을 해주는 방식으로 수행했다.

import Foundation

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

채점 결과

정확성: 15.4
합계: 15.4 / 100.0

반례

```css print(solution(4, [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]])) ``` 당연히 2가 나와야하는데 1이 나오고 있어서 디버깅하다보니..

func dfs(_ current: Int) {
        for (idx, item) in computers[current].enumerated() {
            if item == 1 && !visited[idx] {
                visited[idx] = true
                dfs(item)  // -> item이 아니라 idx !!!! 
            }
        }
    }

item 대신 idx를 해줘야하는데, enumerated()해주는 과정에서 혼동이 있었다..

최종 제출 코드

import Foundation

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

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

---

타인의 코드

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var visit: [Bool] = Array(repeating: false, count: n)
    var answer: Int = 0

    func bfs(_ vertax: Int) {
        visit[vertax] = true
        for i in 0..<n {
            if computers[vertax][i] == 1 && visit[i] == false {
                bfs(i)
            }
        }
    }

    for i in 0..<n {
        if !visit[i] {
            answer += 1
            bfs(i)
        }
    }
    return answer
}

함수명은 bfs긴한데, dfs를 오타내신 것 같다. 최상단에 언급되는 코드와 완전 동일하게 푼 것 같아서, 좀 기분이 좋았다. dfs,bfs는 포맷이 좀 확실해서, 자주 안풀면 헷갈리게 마련이라, 종종 의도적으로 마주쳐야할 듯 !