프로그래머스 네트워크 Swift

Source Code

---

Solution

---

해당 문제는 DFS에 관련된 문제다.

 

1. 컴퓨터와 연결되어있는지 아닌지를 확인한다.

-> 2차원 배열을 만들어 연결된 네트워크들만 모아준다. 즉, 같은 배열에 있는 컴퓨터는 하나의 네트워크이다.

고로 1이라고 연결되어 있는 컴퓨터를 같은 배열에 넣어준다.

 

2. 하나의 컴퓨터라도 연결되어 있으면 하나의 네트워크이므로 각 컴퓨터 마다 연결되어있는 것을 확인하여 재귀로 모든 연결된 컴퓨터의 연결을 확인한다.

ex) 1,2,3,4의 컴퓨터가 있고 1이 234 컴퓨터와 연결되어 있을때 2가 어떤 컴퓨터랑 연결되어있는지 확인 또 2랑 연결된 컴퓨터가 어떤 컴퓨터랑 연결되어 있는지 확인해준다.

 

3.마지막으로 같은 연결로된 네트워크 수를 세어준다.

 

Problem

---

 

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

새롭게 알게 된것

배열 중 어떠한 조건에서 필터링 했을때 맞는 조건의 인덱스만 모으는법

ex)배열 중 값이 0인 인덱스만 한 곳에 모으는법

array.enumrated().filter{$0.element == 0 }.map{$0.offset}

 

다른 사람 풀이

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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 } Colored by Color Scripter

평소엔 테스트만 통과하면 (시간초과가 안나면) 효율적으로 풀었나보다 하고 넘어갔는데 

 

처음으로 다른 사람 풀이랑 각 테스트 케이스별로 시간이 얼마나 걸리는지 확인해보았다.

 

좌측이 다른 사람 풀이,우측이 내 풀이가 걸린 시간인데 10배에서 많게는 20배차이까지 난다...

이젠 풀었다고 그냥 넘어가는 것이 아닌 더 효율적으로 푸는 방법을 고민하고 넘어가야겠다....

 

그래도 처음 3단계로 들어온거치곤 나쁘지 않았다 ㅎㅎㅎ