[Swift] 2022 KAKAO TECH INTERNSHIP 등산코스 정하기

Problem

 

프로그래머스

---

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는 똑같으므로 산봉우리를 만나기까지의 경로만 탐색하면 됐다.

 

요새 릿코드 문제들만 풀다가 오랜만에 프로그래머스 문제를 푸니깐 문제를 읽고 해석하는 것도 시간이 걸렸고 복잡한 시간 초과 룰도 지키기가 까다로웠다...