프로그래머스 - 거리두기 확인하기(Lv. 2)

문제 링크

풀이

import Foundation

func solution(_ places:[[String]]) -> [Int] {
    return places.map { BPS($0) }
}

func BPS(_ place: [String]) -> Int {
    var result = 1  // 0 - 거리두기 안함, 1 - 거리두기 굿
    
    for (i, colum) in place.enumerated() {
        let rows = colum.map { String($0) }
        for (j, row) in rows.enumerated() {
            if row == "P" { // 응시자라면 거리두기 지키는지 확인
                var queue = Queue()
                // 응시자 == 노드
                let node = Node(directions: Direction.cases(i == 0, j == 0, i == 4, j == 4), 
                                position: (i, j))
                let nextNodes = node.getNextNode(place, (i, j)) // 응시자에서 한칸 떨어진 모든 노드들
                queue.enqueues(nextNodes)
                while let dequeue = queue.dequeue() {
                    let pos = dequeue.position
                    let what = place[pos.0].map { String($0) }[pos.1]
                    
                    if what == "P" {    // 거리두기 실패
                        // print("i: \(i) / j: \(j) / pos: \(pos)")
                        result = 0
                        break
                    } else if what == "X" { // 가림막
                        continue
                    } else {
                        if abs(pos.0 - i) + abs(pos.1 - j) < 2 {    // 거리 2이상 멀어진 상태
                            let nextNodes = dequeue.getNextNode(place, (i, j)) // 그 다음 노드 큐에 적재
                            queue.enqueues(nextNodes)
                        }
                    }
                }
            }
        }
    }
    
    return result
}

// 노드가 갈 수 있는 방향
enum Direction {
    case up
    case down
    case left
    case right
    
    // 노드가 갈 수 있는 모든 방향을 가져온다.
    static func cases(_ isFirstColum: Bool, _ isFirstRow: Bool, _ isLastColum: Bool, _ isLastRow: Bool) -> [Direction] {
        var directions: [Direction] = []
        if !isFirstColum {
            directions.append(up)
        }
        if !isFirstRow {
            directions.append(left)
        }
        if !isLastColum {
            directions.append(down)
        }
        if !isLastRow {
            directions.append(right)
        }
        
        return directions
    }
}

struct Node {
    let directions: [Direction]
    let position: (Int, Int)    // 행과 열 위치
    
    func getNextNode(_ place: [String], _ except: (Int, Int)) -> [Node] {
        var nodes: [Node] = []
        for direction in directions {
            var nextPos = position
            switch direction {
                case .up:
                    nextPos = (nextPos.0 - 1, nextPos.1)
                 case .down:
                    nextPos = (nextPos.0 + 1, nextPos.1)
                case .left:
                    nextPos = (nextPos.0, nextPos.1 - 1)
                case .right:
                    nextPos = (nextPos.0, nextPos.1 + 1)
            }
            
            if nextPos.0 == except.0 && nextPos.1 == except.1 {
                continue
            }
            
            let node = Node(directions: Direction.cases(nextPos.0 == 0, nextPos.1 == 0, 
                                                        nextPos.0 == 4, nextPos.1 == 4), 
                                position: nextPos)
            nodes.append(node)
        }
        
        return nodes
    }
}

struct Queue {
    var array: [Node?] = []
    var index = 0
    
    mutating func enqueue(_ node: Node) {
        array.append(node)
    }
    
    mutating func enqueues(_ nodes: [Node]) {
        array.append(contentsOf: nodes)
    }
    
    mutating func dequeue() -> Node? {
        if array.count > index {
            let node = array[index]
            array[index] = nil
            index += 1
            return node
        } else {
            return nil
        }
    }
}

후기

라인수 126... 지금까지 코테 푼것중에 제일 코드를 많이 짜지 않았나 생각든다.
깊이/넓이 우선탐색을 써서 풀어야할 문제인데 본인은 문제 특성상 넓이 우선탐색을 사용하였다.
(거처온 경로에 대해서 체크할 필요도 없고 특정 노드를 거치면 그 이후것을 탐색할 필요가 없기에 BFS가 맞다고 생각한다.)

이시국에 걸맞는 재밌는 문제였다.