[Swift 알고리즘] 프로그래머스(Lv.4) - 동굴 탐험 / 2020 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.4) - 동굴 탐험" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 동굴 탐험

 

---

풀이

이번 문제는 그래프 탐색 문제입니다.

특정 노드를 방문하기 전까지 방문할 수 없는 노드가 있다는 것이 특이한 점입니다.

노드의 개수는 2 이상 20만 이하로 O(n) 또는 O(nlogn)으로 해결해야 합니다.

저는 시간 복잡도를 줄이기 위해 Dictionary를 적극적으로 사용했습니다.

 

bfs가 아닌 dfs를 선택한 이유도 시간 복잡도 때문입니다.

popLast()를 이용하기 위해 dfs를 선택했습니다.

 

0. Root 노드를 방문하지 못하는 케이스를 예외 처리 합니다.

테스트 케이스 중 root 노드를 방문하지 못하는 케이스가 존재합니다.

이 케이스를 예외처리 해주지 않으면 30번 테스트 케이스가 실패합니다.

코드 순서는 2번 이후에 진행했습니다.

if let _ = waitingDict[0] {
    return false
}

 

1. 양방향 그래프를 생성합니다.

그래프는 평범한 방법으로 생성했습니다.

 

2. order는 두 가지 Dictionary에 나눠서 처리했습니다.

closeDict는 order[0]을 키로 갖는 딕셔너리이고 waitingDict는 order[1]을 키로 갖는 딕셔너리입니다.

closeDict는 노드를 방문할 때 Open할 수 있는 노드가 있는지 체크합니다.

waitingDict는 현재 방문을 하지 못하는 노드인지 체크하는데 사용합니다.

 

3. dfs에 필요한 배열을 만듭니다.

- needVisited: 방문할 노드를 담는 스택 역할. root 노드인 0을 담아서 초기화 합니다.

- visited: 이미 방문한 노드인지 체크하는 역할(방문하면 true)

- waiting: 방이 open되고 다시 방문해야 하는 곳을 담는 배열(Open된 노드 중 방문을 대기 중이면 true)

 

4. dfs를 시작합니다!

popLast()를 하며 node를 꺼내고 visited[node] = true 를 수행합니다.

 

4-1. 꺼낸 노드가 닫힌 node 중 하나를 열 수 있는지 확인합니다.

열 수 있다면 그 노드가 이미 방문했던 노드인지 체크합니다.

이미 방문한 닫힌 노드는 Open하면 바로 방문할 수 있기 때문에 따로 체크하는 것입니다.

따라서 이 경우에는 Open 직후 needVisited 배열에 append 합니다.

그게 아니라면 Open만 합니다.

 

4-2. 다음 node를 탐색합니다.

연결된 노드 중 닫혀 있지 않은 노드는 바로 needVisited 배열에 append 합니다.

만약 닫혀 있다면 open합니다.

 

5. 결과 출력

마지막까지 닫힌 노드가 있다면 false입니다.

이는 closeDict가 비었는지 체크하면 알 수 있습니다.

 

후기

너무 어려웠던 문제입니다...

같이 스터디하는 친구에게 흐름만 조언 받고 직접 구현해보았습니다.

 

감사합니다! 

---

전체 코드

import Foundation

func solution(_ n:Int, _ path:[[Int]], _ order:[[Int]]) -> Bool {
    var graph: [Int: [Int]] = [:]
    for i in 0..<n {
        graph[i] = []
    }
    
    path.forEach {
        graph[$0[0]]?.append($0[1])
        graph[$0[1]]?.append($0[0])
    }
    
    var waitingDict: [Int:Int] = [:]
    var closeDict: [Int:Int] = [:]
    order.forEach { 
        closeDict[$0[0]] = $0[1]
        waitingDict[$0[1]] = $0[0]
    }
    
    if let _ = waitingDict[0] {
        return false
    }
    
    var needVisited: [Int] = [0]
    var waiting: [Bool] = Array(repeating: false, count: n)
    var visited: [Bool] = Array(repeating: false, count: n)
    
    while !needVisited.isEmpty {
        let node = needVisited.popLast()!
        visited[node] = true
        
        if let opened = closeDict[node] {
            closeDict[node] = nil
            if waiting[opened] {
                waiting[opened] = false
                needVisited.append(opened)
            } else {
                waitingDict[opened] = nil
            }
        }

        for n in graph[node]! {
            if !visited[n] && !waiting[n] {
                if let _ = waitingDict[n] {
                    waitingDict[n] = nil
                    waiting[n] = true
                } else {
                    needVisited.append(n)    
                }
            }
        }
    }
    
    return closeDict.isEmpty
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.