[프로그래머스] 2021 카카오 채용연계형 인턴십 거리두기 확인하기 with Swift

안녕하세요! 오늘은 프로그래머스 2레벨 거리두기 확인하기 문제를 풀어보겠습니다!

이번 문제는 맨허튼 거리를 이용해서 거리를 확인하는 문제입니다!

 

소스 코드량(함수로 안만들어서 뻥튀기된 부분이 있어요 ㅠㅠ)에 비해서 생각보다 문제가 쉬우니 다들 풀어보시기 바랍니다!

 

 

우선 이 문제는 사람이 앉은 포인트를 잡아서 맨허튼 거리 2안에서 사람이 또 있는지 없는지를 확인하는 문제입니다!

 

장애물도 있기 때문에 일반적인 거리측정방법말고 DFS나 BFS를 이용해야합니다.

 

저번에 DFS로 문제를 풀었던게 있어서 BFS로 문제를 풀어보겠습니다!

 

우선 BFS에 쓸 Queue가 필요한데 Swift에는 기본적으로 지원해주는 Queue가 없으니 대충 만들어 씁시다!

 

Queue도 거리가 2까지이다 보니 Queue도 완벽하게 구현할 필요없어보여 기능만 똑같은 dequeue에 손해를 보는 Queue로 만들었습니다!

struct Queue<T> {
    public var queue:[T] = []
    
    public var count:Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ data: T) {
        queue.append(data)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

 

그리고 for문을 돌리기 편하게 문자열로된 입력을 Int배열로 바꿔줍시다!

for i in 0..<5 {
    map.append([])
    for j in 0..<5 {
        if places[count][i][places[count][i].index(places[count][i].startIndex, offsetBy: j)] == "P" {
            map[i].append(1)
        }
        else if places[count][i][places[count][i].index(places[count][i].startIndex, offsetBy: j)] == "O" {
            map[i].append(0)
        }
        else if places[count][i][places[count][i].index(places[count][i].startIndex, offsetBy: j)] == "X" {
            map[i].append(2)
        }
    }
}

그리고 bfs Queue에 처음에 시작할 위치를 넣어주고 dequeue를 하면서 4방향에 넣을수 있는 방향을 enqueue해주는 것을 반복하면 서 결과를 answer에 넣어주시면 문제가 해결됩니다!

 

import Foundation

struct Queue<T> {
    public var queue:[T] = []
    
    public var count:Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ data: T) {
        queue.append(data)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

let directions:[[Int]] = [[0,1],[0,-1],[1,0],[-1,0]]

func solution(_ places:[[String]]) -> [Int] {
    
    var answer:[Int] = []
    let isVisitedMapReference = [[Int]](repeating: [0,0,0,0,0], count: 5)
    
    for count in 0..<5 {
        var map:[[Int]] = [[]]
        
        for i in 0..<5 {
            map.append([])
            
            for j in 0..<5 {
            
                if places[count][i][places[count][i].index(places[count][i].startIndex, offsetBy: j)] == "P" {
                    map[i].append(1)
                }
                
                else if places[count][i][places[count][i].index(places[count][i].startIndex, offsetBy: j)] == "O" {
                    map[i].append(0)
                }
                
                else if places[count][i][places[count][i].index(places[count][i].startIndex, offsetBy: j)] == "X" {
                    map[i].append(2)
                }
            }
        }
        
        var keepDistance = true
        bfsLoop : for i in 0..<5 {
            for j in 0..<5 {
                
                if map[i][j] != 1 {
                    continue
                }
                
                var queue:Queue<[Int]> = Queue<[Int]>()
                var isVisitedMap = isVisitedMapReference
                isVisitedMap[i][j] = 1
                var manhattanDistance = 0
                queue.enqueue([i, j])
                repeat {
                    manhattanDistance += 1
                    if manhattanDistance > 2 {
                        break 
                    }
                    
                    let count = queue.count
                    for queueCount in 0..<count {
                        let point = queue.dequeue()
                        for direction in directions {
                            var dx = point![0] + direction[0]
                            var dy = point![1] + direction[1]

                            if dx < 0 || dy < 0 || dy > 4 || dx > 4 {
                                continue
                            }

                            if isVisitedMap[dx][dy] == 1 {
                                continue
                            }

                            if map[dx][dy] == 2 {
                                continue
                            }

                            if map[dx][dy] == 1 {
                                keepDistance = false
                                answer.append(0)
                                break bfsLoop
                            }

                            isVisitedMap[dx][dy] = 1
                            queue.enqueue([dx, dy])
                        }
                    }
                } while queue.isEmpty != true
            }
        }
        
        if keepDistance == true {
            answer.append(1)
        }
    }
    return answer
}

오늘은 여기까지이며 잘 이해되지 않으시는게 있으시면 질문해주세요!

 

감사합니다!