백준 9328번 열쇠 (swift) [G1]

BFS

1. 시작점 큐에 넣기
2. 반복
   1. 큐에서 꺼내기
   2. 방문 체크하기
   3. 갈 수 있는 곳이자 안 간 곳 큐에 넣기

생각회로

1. 테두리 BFS 반복 -> 시간초과 ( 100개의 테케를 얕봤다. )
2. 열쇠 찾을 때만 다음 BFS 진행 -> 시간초과
3. 배열로 큐 대신 큐 구현( 스택 두개로 ) -> 시간초과
4. 열쇠 찾으면 모든 문 열기 -> 시간초과
5. 열쇠 찾으면 해당 열쇠 모두 제거 -> 시간초과
6. 초기 열쇠 중복 제거 -> 시간초과
7. 테두리 매 번 찾는 대신, startingPoints 한 번만 구해두기 -> 시간초과
8. 알파벳 배열에 미리저장 대신, Swift 5 부터 추가된 Character.isUppercase 사용 -> 시간초과
9. 문이지만 갈 곳 추가하기 대신, 문이면 안 가기 ( 열쇠 발견시 초기화때문 ) -> 시간초과
10. 시작점이 간 곳이여도 탐색하는 오류 제거 -> 통과
    

주의사항

• BFS를 얕보지 말자
  100(테케)*100(가로)*100(세로)*26(알파벳)*BFS횟수
  == 2600만 * BFS횟수

소스코드

import Foundation

class Queue {
    var enqueue = [(Int,Int)]()
    var dequeue = [(Int,Int)]()
    
    func pop() -> (Int, Int)? {
        if dequeue.isEmpty{
            if enqueue.isEmpty{
                return nil
            }else{
                dequeue = enqueue.reversed()
                enqueue.removeAll()
            }
        }
        return dequeue.popLast()!
    }
    
    func append(_ element: (Int,Int) ) {
        enqueue.append(element)
    }
    
    var isEmpty: Bool {
        enqueue.isEmpty && dequeue.isEmpty
    }
}

class Solution {
    var li: [[String]] // O(100*100)
    var keys: [String] // 알파벳 contains - O(26)
    
    let ix = [0,0,1,-1] // 4
    let iy = [1,-1,0,0]
    var answer: Int = 0
    
    var startPoints = [(Int,Int)]()
    
    init(li: [[String]], keys: [String]) {
        self.li = li
        self.keys = keys
    }
    
    func findOutLine() { // 어차피 갈 곳은 정해져있다. ( 빈칸으로만 찾으면 안 됨)
        for i in 0..<li.count{
            if li[i][0] != "*"{
                startPoints.append((i,0))
            }
            if li[i][li[0].count - 1] != "*" {
                startPoints.append((i, li[0].count - 1))
            }
        }
        
        for i in 0..<li[0].count{
            if li[0][i] != "*"{
                startPoints.append((0, i))
            }
            if li[li.count - 1][i] != "*" {
                startPoints.append((li.count - 1, i))
            }
        }
    }
    
    func solve() {
        findOutLine()
        keys.forEach{ foundKeySoClearAllOfDoors($0) } // 미리 다 열어두고 열쇠도 줍는다.
        
        while searchFromOutline() { // 키 찾으면 다시함
        }
        print(answer)
    }
    
    
    func foundKeySoClearAllOfDoors(_ key: String) {
        for i in 0..<li.count{
            for j in 0..<li[0].count{
                if keys.contains(li[i][j].lowercased()){
                    li[i][j] = "."
                }
            }
        }
        keys.removeAll()
    }
    
    func searchFromOutline() -> Bool {
        let q = Queue()
        q.dequeue = startPoints
        
        return search(q, li)
    }
    
    func search(_ q: Queue,_ _thisLi:[[String]]) -> Bool {
        var thisLi = _thisLi
        var ret = false
        while !q.isEmpty {
            let (X, Y) = q.pop()!
            
            if thisLi[X][Y] == "@"{
                continue
            }

            if li[X][Y] == "$" {
                answer += 1
                li[X][Y] = "."
            }
            
            if (li[X][Y].first!).isLowercase { // 키일경우
                keys.append(li[X][Y])
                li[X][Y] = "."
                return true // 다시해
            }
            
            if (li[X][Y].first!).isUppercase { // 잠겼을 경우
                if keys.contains(li[X][Y].lowercased()) { // 키가 있으면
                    li[X][Y] = "."
                }else{
                    continue
                }
            }
            
            thisLi[X][Y] = "@"
            
            for i in 0..<ix.count { // 다음 탐색
                let (nextX, nextY) = (X+ix[i], Y+iy[i])
                if nextX < 0 || nextY < 0 || nextX >= li.count || nextY >= li[0].count{
                    continue
                }
                if ["*","@"].contains(thisLi[nextX][nextY]) {
                    continue
                }
                
                q.append((nextX, nextY))
            }
            
        }
        return ret
    }
}

func main() {
    let T = Int(readLine()!)!
    (0..<T).forEach{ _ in
        let hw = readLine()!.split(separator: " ").map{Int($0)!}
        var li = Array(repeating: Array(repeating: "", count: hw[1]), count: hw[0])
        (0..<hw[0]).forEach{ i in li[i] = readLine()!.map{ String($0)} }
        let keys = Set(readLine()!.map{String($0)})
        let solution = Solution(li: li, keys: keys.contains("0") ? [] : Array(keys))
        solution.solve()
    }
}

main()