๐Ÿ“– Problem Solution/Programmers

[Swift] 2022 KAKAO TECH INTERNSHIP ๋“ฑ์‚ฐ์ฝ”์Šค ์ •ํ•˜๊ธฐ

Fomagran ๐Ÿ’ป 2022. 8. 29. 08:22
728x90
๋ฐ˜์‘ํ˜•

Problem

 

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr


Solution

 

ํ•ด๋‹น ๋ฌธ์ œ๋Š” BFS ํ˜น์€ ๋‹ค์ต์ŠคํŠธ๋ผ๋ฅผ ์ด์šฉํ•˜์—ฌ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

1. ํ˜„์žฌ ๊ฒฝ๋กœ์˜ ์ตœ๋Œ€ intensity์™€ ํ˜„์žฌ ์ง€์ ์˜ ์ •๋ณด๋ฅผ ๊ฐ–๋Š” Node๋ฅผ ๋งŒ๋“ค์–ด ์ค€๋‹ค.

 

struct Node {
    let current: Int
    let maxIntensity: Int
}

 

2. ํ•„์š”ํ•œ ๋ณ€์ˆ˜๋“ค์„ ์„ธํŒ…ํ•ด ์ค€๋‹ค.

 

answer: ๊ฐ€์žฅ ์ ์€ intensity์˜ ์‚ฐ๋ด‰์šฐ๋ฆฌ์™€ ๊ฐ’์„ ์ €์žฅํ•  ๋ณ€์ˆ˜

connection: path์˜ ์—ฐ๊ฒฐ๋œ ์ •๋ณด๋ฅผ ์ €์žฅํ•  ๋ณ€์ˆ˜

summitDic: ์‚ฐ๋ด‰์šฐ๋ฆฌ๋ฅผ ์ €์žฅํ•  ๋”•์…”๋„ˆ๋ฆฌ

gateDic: ๊ฒŒ์ดํŠธ๋ฅผ ์ €์žฅํ•  ๋”•์…”๋„ˆ๋ฆฌ

bfsQueue: bfs๋ฅผ ์ง„ํ–‰ํ•  ๋•Œ Node๋ฅผ ๋‹ด์€ ํ

intensities: ๊ฐ ์ง€์ ์˜ ์ตœ๋Œ€ intensity๋ฅผ ์ €์žฅํ•  ๋ฐฐ์—ด

 

    var answer: [Int] = [Int.max,Int.max]
    var connection: [Int:[[Int]]] = [:]
    var summitDic: [Int:Bool] = [:]
    var gateDic: [Int:Bool] = [:]
    var bfsQueue: [Node] = []
    var intensities: [Int] = Array(repeating: Int.max, count: n+1)

 

3. summit, gate, path๋ฅผ ์„ธํŒ…ํ•ด ์ค€๋‹ค.

 

    for summit in summits {
        summitDic[summit] = true
    }
    
    for gate in gates {
        gateDic[gate] = true
    }
    
    for path in paths {
        connection[path[0],default:[]].append([path[1],path[2]])
        connection[path[1],default:[]].append([path[0],path[2]])
    }

 

4. gate๋งˆ๋‹ค bfs๋กœ ํƒ์ƒ‰ํ•œ๋‹ค.

 

bfsQueue์— ํ•ด๋‹น ๊ฒŒ์ดํŠธ ์ •๋ณด๋ฅผ ๋„ฃ๊ณ  bfs๋กœ ํƒ์ƒ‰ํ•ด ์ค€๋‹ค.

 

bfsQueue๊ฐ€ ๋ชจ๋‘ ์—†์–ด์งˆ ๋•Œ๊นŒ์ง€ checkNextNode๋กœ ๋‹ค์Œ ์ง€์ ์œผ๋กœ ์ด๋™ํ•  ํ•„์š”๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•ด ์ค€๋‹ค.

 

    for gate in gates {
        bfsQueue.append(Node(current: gate, maxIntensity: -1))
        bfs()
    }
    
    func bfs() {
        while !bfsQueue.isEmpty {
            let first = bfsQueue.removeFirst()
            checkNextNode(first)
        }
    }

 

5. ํ˜„์žฌ ์ง€์ ๊ณผ ์—ฐ๊ฒฐ๋œ ์ง€์  ์ค‘ ํƒ์ƒ‰ํ•  ํ•„์š”๊ฐ€ ์žˆ๋Š”์ง€๋ฅผ ์ฒดํฌํ•œ๋‹ค.

 

๋จผ์ € ํ•ด๋‹น ๋…ธ๋“œ๊ฐ€ ์‚ฐ๋ด‰์šฐ๋ฆฌ๋ผ๋ฉด ์ด๋ฏธ ๋ชฉํ‘œ์— ๋„์ฐฉํ•œ ๊ฒƒ์ด๋ฏ€๋กœ ํƒ์ƒ‰ํ•˜์ง€ ์•Š์•„๋„ ๋œ๋‹ค.

 

(์นด์นด์˜ค ํ•ด์„ค์„ ์ฐธ๊ณ ํ•˜๋ฉด ์–ด์ฐจํ”ผ ์™•๋ณต์ด๋‚˜ ์‚ฐ๋ด‰์šฐ๋ฆฌ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒƒ์ด๋‚˜ ์ตœ๋Œ€ intensity๋Š” ๋˜‘๊ฐ™์œผ๋ฏ€๋กœ ์‚ฐ๋ด‰์šฐ๋ฆฌ๋กœ ๋‹จ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•˜๋Š” ๊ฒƒ๋งŒ ์ฒดํฌํ•˜๋ฉด ๋œ๋‹ค.)

 

๋˜ํ•œ ํ•ด๋‹น ์ง€์ ์˜ ์ตœ๋Œ€์น˜๋ณด๋‹ค ํ˜„์žฌ ๋…ธ๋“œ์˜ ์ตœ๋Œ€์น˜๊ฐ€ ์ •๋‹ต์ด ๋  ์ˆ˜ ์—†์œผ๋ฏ€๋กœ ํƒ์ƒ‰์„ ์ค‘๋‹จํ•œ๋‹ค.

 

    func checkNextNode(_ node: Node) {
        if summitDic[node.current] != nil || node.maxIntensity > intensities[node.current] {
            return
        }
        ...

 

์œ„ ๋‘ ๊ฒฝ์šฐ๊ฐ€ ๋ชจ๋‘ ์•„๋‹ˆ๋ผ๋ฉด ์ด์ œ ํ˜„์žฌ ๋…ธ๋“œ์™€ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ ์ค‘ gate๊ฐ€ ์•„๋‹Œ ๋…ธ๋“œ๋“ค ํƒ์ƒ‰ํ•œ๋‹ค.

 

๋จผ์ € ํ˜„์žฌ ๊ฒฝ๋กœ์˜ ๊ฐ€์žฅ ์ตœ๋Œ€ intensity์™€ ๋‹ค์Œ์œผ๋กœ ์ด์–ด์งˆ intensity๋ฅผ ๋น„๊ตํ•ด maxIntensity๋ฅผ ์ •ํ•œ๋‹ค.

 

๋งŒ์•ฝ maxIntensity๊ฐ€ ํ•ด๋‹น ์ง€์ ์˜ ์ตœ๋Œ€ intensity๋ณด๋‹ค ์ ๋‹ค๋ฉด ํ•ด๋‹น ์ง€์ ์˜ intensity๋ฅผ maxIntensity๋กœ ๊ฐฑ์‹ ํ•ด ์ฃผ๊ณ  bfsQueue์— ํ•ด๋‹น ์ •๋ณด๋ฅผ ๋„ฃ์–ด์ค€๋‹ค.

 

๊ทธ ๋‹ค์Œ updateAnswer๋กœ ์ •๋‹ต๋„ ๊ฐฑ์‹ ํ•ด ์ฃผ๋Š”๋ฐ ๋ฐ‘์—์„œ ์„ค๋ช…ํ•˜๊ฒ ๋‹ค.

 

        ...
        for next in connection[node.current,default:[]] where gateDic[next[0]] == nil {
            let maxIntensity = max(node.maxIntensity,next[1])
            
            if maxIntensity < intensities[next[0]] {
                updateAnswer(next[0], maxIntensity)
                intensities[next[0]] = maxIntensity
                bfsQueue.append(Node(current: next[0], maxIntensity:maxIntensity))
            }
        }
    }

 

6. maxIntensity์˜ ์ •๋ณด๋กœ answer๋ฅผ ๊ฐฑ์‹ ํ•ด ์ค€๋‹ค.

 

๋งŒ์•ฝ ํ•ด๋‹น ์ง€์ ์ด ์‚ฐ๋ด‰์šฐ๋ฆฌ๊ณ  answer์˜ ์ตœ์†Œ๊ฐ’๋ณด๋‹ค ์ ๋‹ค๋ฉด ํ•ด๋‹น ์ง€์ (index)์™€ maxIntensity๋กœ ๊ฐฑ์‹ ํ•ด ์ค€๋‹ค.

 

๋งŒ์•ฝ answer์˜ ์ตœ๋Œ“๊ฐ’๊ณผ maxIntensity๊ฐ€ ๊ฐ™๋‹ค๋ฉด ์‚ฐ๋ด‰์šฐ๋ฆฌ์˜ ์ง€์ ์ด ๋” ๋‚ฎ์€ ๊ฒƒ์œผ๋กœ ๊ฐฑ์‹ ํ•ด ์ค€๋‹ค.

 

    func updateAnswer(_ index: Int,_ maxIntensity: Int) {
        if summitDic[index] != nil {
            if maxIntensity == answer[1] {
                answer[0] = min(answer[0],index)
            } else if maxIntensity < answer[1] {
                answer = [index,maxIntensity]
            }
        }
    }

 

7. answer๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

    return answer

Result

 


Source Code

 

struct Node {
    let current: Int
    let maxIntensity: Int
}

func solution(_ n:Int, _ paths:[[Int]], _ gates:[Int], _ summits:[Int]) -> [Int] {
    var answer: [Int] = [Int.max,Int.max]
    var connection: [Int:[[Int]]] = [:]
    var summitDic: [Int:Bool] = [:]
    var gateDic: [Int:Bool] = [:]
    var bfsQueue: [Node] = []
    var intensities: [Int] = Array(repeating: Int.max, count: n+1)
    
    for summit in summits {
        summitDic[summit] = true
    }
    
    for gate in gates {
        gateDic[gate] = true
    }
    
    for path in paths {
        connection[path[0],default:[]].append([path[1],path[2]])
        connection[path[1],default:[]].append([path[0],path[2]])
    }

    func checkNextNode(_ node: Node) {
        if summitDic[node.current] != nil || node.maxIntensity > intensities[node.current] {
            return
        }
        
        for next in connection[node.current,default:[]] where gateDic[next[0]] == nil {
            let maxIntensity = max(node.maxIntensity,next[1])
            
            if maxIntensity < intensities[next[0]] {
                updateAnswer(next[0], maxIntensity)
                intensities[next[0]] = maxIntensity
                bfsQueue.append(Node(current: next[0], maxIntensity:maxIntensity))
            }
        }
    }
    
    func bfs() {
        while !bfsQueue.isEmpty {
            let first = bfsQueue.removeFirst()
            checkNextNode(first)
        }
    }

    for gate in gates {
        bfsQueue.append(Node(current: gate, maxIntensity: -1))
        bfs()
    }
    
    func updateAnswer(_ index: Int,_ maxIntensity: Int) {
        if summitDic[index] != nil {
            if maxIntensity == answer[1] {
                answer[0] = min(answer[0],index)
            } else if maxIntensity < answer[1] {
                answer = [index,maxIntensity]
            }
        }
    }
                                  
    return answer
}

P.S

 

์ฒ˜์Œ์— ๊ทธ๋ƒฅ DFS๋กœ ๊ฒฝ๋กœ๋ฅผ ํ•œ๋ฒˆ ํƒ์ƒ‰ํ•œ ๋‹ค์Œ ์ตœ์†Œ intensity๋ฅผ ์ฐพ์•„์•ผ์ง€ ํ–ˆ๋Š”๋ฐ ์–ด๊น€์—†์ด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜์™”๋‹ค.

 

๋‹ค์‹œ ์ƒ๊ฐํ•ด ๋ณด๋‹ˆ๊น BFS๋กœ ํ•ด๋‹น ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ์ตœ๋Œ€๊ฐ’๋ณด๋‹ค ์ ๋‹ค๋ฉด ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•˜๊ณ  ์•„๋‹ˆ๋ผ๋ฉด ํƒ์ƒ‰์„ ํ•˜์ง€ ์•Š์•„์ค˜๋„ ๋๋‹ค.

 

๋˜ gate์—์„œ ์ถœ๋ฐœํ•˜์—ฌ gate๋กœ ๋„์ฐฉํ•  ์‹œ์— ํ•ด๋‹น ์ตœ์†Œ intensity๋ฅผ ๊ฐฑ์‹ ํ•˜๋Š” ์‹์œผ๋กœ ํ–ˆ๋”๋‹ˆ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜์™€์„œ ์นด์นด์˜ค ํ•ด์„ค์„ ๋ณด๋‹ˆ๊น

 

์‚ฐ๋ด‰์šฐ๋ฆฌ๊นŒ์ง€ ์™•๋ณต์œผ๋กœ ํƒ์ƒ‰ํ•˜๋‚˜ ์‚ฐ๋ด‰์šฐ๋ฆฌ๊นŒ์ง€ ๋‹จ๋ฐฉํ–ฅ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋‚˜ maxIntensity๋Š” ๋˜‘๊ฐ™์œผ๋ฏ€๋กœ ์‚ฐ๋ด‰์šฐ๋ฆฌ๋ฅผ ๋งŒ๋‚˜๊ธฐ๊นŒ์ง€์˜ ๊ฒฝ๋กœ๋งŒ ํƒ์ƒ‰ํ•˜๋ฉด ๋๋‹ค.

 

์š”์ƒˆ ๋ฆฟ์ฝ”๋“œ ๋ฌธ์ œ๋“ค๋งŒ ํ’€๋‹ค๊ฐ€ ์˜ค๋žœ๋งŒ์— ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ๋ฌธ์ œ๋ฅผ ํ‘ธ๋‹ˆ๊น ๋ฌธ์ œ๋ฅผ ์ฝ๊ณ  ํ•ด์„ํ•˜๋Š” ๊ฒƒ๋„ ์‹œ๊ฐ„์ด ๊ฑธ๋ ธ๊ณ  ๋ณต์žกํ•œ ์‹œ๊ฐ„ ์ดˆ๊ณผ ๋ฃฐ๋„ ์ง€ํ‚ค๊ธฐ๊ฐ€ ๊นŒ๋‹ค๋กœ์› ๋‹ค...

728x90
๋ฐ˜์‘ํ˜•