[프로그래머스/Swift] 81302번 - 거리두기 확인하기

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/81302

💡 구현 아이디어

1. 좌사단 → 우하단으로 이동하면서 자리에 사람이 있으면 큐에 넣고 큐가 빌때까지 확인 진행
2. 해당 자리까지 거리가 3미만이면 조건확인
3. 빈자리면 큐에 넣음 / 사람이면 0으로 즉시 종료 / 파티션이면 무시
4. 우하단까지 최종적으로 확인이 되면 1을 반환
5. 총 5번 반복

💻 코드

import Foundation

func solution(_ places:[[String]]) -> [Int] {
    var result: [Int] = []
    for place in places {
        result.append(isComplete(input: place))
    }
    return result
}

func isComplete(input: [String]) -> Int {
    let map = input.map { Array($0).map { String($0) } }
    var checkMap: [[Bool]] = [[Bool]](repeating: [Bool](repeating: true, count: 5), count: 5)
    var queue: [(x: Int, y: Int, len: Int)] = []
    let movePoint: [[Int]] = [[-1, 0], [1, 0], [0, -1], [0, 1]] // 좌우상하
    
    for y in 0..<5 {
        for x in 0..<5 {
            // 현재 위치에 사람이 있으면 확인
            if map[y][x] == "P" {
                
                // queue 초기화 
                queue = []
                queue.append((x: x, y: y, len: 0))
                var idx: Int = 0
                
                while idx < queue.count {
                    let p0 = queue[idx]
                    checkMap[p0.y][p0.x] = false
                    
                    for mp in movePoint {
                        // 확인할 위치
                        let p1 = (
                            x: p0.x + mp[0],
                            y: p0.y + mp[1],
                            len: p0.len + 1
                        )
                        
                        // 거리 3미만일 때만 확인하면 됨
                        if p1.x >= 0 && p1.x < 5 && p1.y >= 0 && p1.y < 5 &&  p1.len < 3 {
                            // 이전에 확인안했음
                            if checkMap[p1.y][p1.x] {
                                // 확인할 위치에 사람이 있음 - 거리안지킴 
                                if map[p1.y][p1.x] == "P" {
                                    return 0
                                }
                                // 확인할 위치가 빈자림임 - 큐에 등록
                                if map[p1.y][p1.x] == "O" {
                                    queue.append(p1)
                                }
                            }
                        }
                    }
                    
                    idx += 1
                }
            }
        }
    }
    return 1
}

❌ 틀린 이유 및 틀린 부분

⏳ 시간 복잡도

O(N^2) : 각 5개 구역에 대해 전체 칸을 한번씩 접근, 각 칸에 대해서 최악의경우 좌우상단 거리2까지 확인 = 5 * (55) * (44) = 2000번

📌 풀이 또는 기억할 정보