?_백준_2606 swift

https://www.acmicpc.net/problem/2606

 

 

 

 

 

실패

사유 : 메모리 초과

map이란 Dict의 value가 [Int]이기 때문인 것으로 추정

let count = Int(readLine()!)!
let connection = Int(readLine()!)!
var inputList = [[Int]]()

for _ in 0..<connection {
    let tempStr = readLine()!
    let result = tempStr.components(separatedBy: " ").map({Int($0)!})
    inputList.append(result)
}


var infection = 0
var stack : [Int] = []
var map = [Int:[Int]]()

func mapping(list: [[Int]]) {
    for rep in list {
        if map[rep[0]] == nil {
            map[rep[0]] = []
        }
        map[rep[0]]?.append(rep[1])
    }
}

func sol(count: Int, connection: Int, list: [[Int]]) -> Int {
    mapping(list: list)
    
    let filtered = list.filter({
        $0[0] == 1
    })
    
    for rep in filtered {
        infection += 1
        stack.append(rep[1])
    }
    
    while !stack.isEmpty {
        if stack.isEmpty {
            break
        }
        let rep = stack.removeLast()
        
        if map[rep] == nil {
            continue
        }
        
        for infected in map[rep]! {
            infection += 1
            stack.append(infected)
        }
    }
    
    return infection
}

print(sol(count: count, connection: connection, list: inputList))

 

실패 2

메모리 초과가 이유라면 무식하게 filter를 사용해서..?

-> 시간초과

import Foundation

let count = Int(readLine()!)!
let connection = Int(readLine()!)!
var inputList = [[Int]]()

for _ in 0..<connection {
    let tempStr = readLine()!
    let result = tempStr.components(separatedBy: " ").map({Int($0)!})
    inputList.append(result)
}

var infection = 0
    var stack : [Int] = []
    
    func sol(count: Int, connection: Int, list: [[Int]]) -> Int {
        
        let filtered = list.filter({
            $0[0] == 1
        })
        
        for rep in filtered {
            infection += 1
            stack.append(rep[1])
        }
        
        while !stack.isEmpty {
            let rep = stack.removeLast()
            let repFiltered = list.filter({
                $0[0] == rep
            })
            
            for infected in repFiltered {
                infection += 1
                stack.append(infected[1])
            }
        }
        
        return infection
    }

print(sol(count: count, connection: connection, list: inputList))

 

 

실패3

그..렇다면? 그래프와 dfs를 접목해서..?

import Foundation

let count = Int(readLine()!)!
let connection = Int(readLine()!)!
var inputList = [[Int]]()

for _ in 0..<connection {
    let tempStr = readLine()!
    let result = tempStr.components(separatedBy: " ").map({Int($0)!})
    inputList.append(result)
}

    
    class Chain {
        let nod : Int
        var nexts = [Int]()
        
        init(nod: Int) {
            self.nod = nod
        }
    }
    
    var infection = 0
    var chains = [Chain]()
    
    func sol(count: Int, connection: Int, list: [[Int]]) -> Int {
        
        for i in 1...count {
            chains.append(Chain.init(nod: i))
        }
        
        for rep in list {
            chains[rep[0] - 1].nexts.append(rep[1])
        }
        
        recursion(now: 1)
        
        return infection
    }
    
    func recursion(now: Int) {
        let nexts = chains[now - 1].nexts
        infection += nexts.count
        
        for rep in nexts {
            recursion(now: rep)
        }
    }

print(sol(count: count, connection: connection, list: inputList))

 

연결을 좌 우로 나눠서 탐색

지금은 탑다운 방식이지만, 좌 우로 나눠서 상호간의 탐색이 가능하도록 하는게 key