카카오인턴십 BFS문제, 거리두기 확인하기 swift풀이

---

프로그래머스 2단계 거리두기 확인하기 문제설명

오늘은 카카오인턴 문제 중 거리두기 확인하기 문제를 풀어보겠습니다.
응시자("P"), 빈테이블("0"), 파티션("X")으로 이루어진 문자열 배열을 여러개 가진 [[String]] 타입 인자가 주어질때, 인자에 주어지는 각각의 [String]타입 문자열배열 맵이 거리두기를 준수하는지를 보는 문제입니다. 문제에 대한 자세한 설명은 아래 링크를 참고하시기 바랍니다.

카카오인턴 BFS문제, 거리두기 확인하기 문제링크 ▼

코딩테스트 연습 - 거리두기 확인하기

거리두기 준수 여부는 각각의 [String] 타입 배열 맵에서 응시자들 간의 거리가 칸막이가 없는 맨해튼거리 2를 초과해서 거리를 두고 있는지를 판단하여 준수할 경우 1을, 준수하지 않을 경우 0을 반환합니다. 그렇게 여러개 있는 각 맵의 거리두기 준수여부를 [Int]타입 배열로 반환합니다. 예를들어 첫번째, 세번째 맵은 준수를 했고 2, 4, 5번째 맵이 준수를 안했다면 [1, 0, 1, 0, 0] 과 같은 결과값을 반환하면 됩니다.

바로 swift언어로 거리두기 확인하기 문제 풀어보도록 하겠습니다. 저는 BFS, 너비우선탐색 방식으로 접근해서 풀어보겠습니다.

---

프로그래머스 2단계 거리두기 확인하기 문제 swift BFS 풀이

3행) BFS 탐색 중 큐 타입으로 사용할 Tuple 타입을 정의했습니다. x, y좌표와 맨해튼 거리 준수여부를 체크할 dist 거리변수를 두었습니다.
4 ~ 5행) dx, dy는 BFS 4방향 탐색을 위해 사용되는 값으로, 기존좌표 기준 x, y좌표 이동방향 추가해야할 값을 정의한 배열입니다. 인덱스 0부터 3까지 순서대로 우->좌->상->하를 한칸 이동하기 위한 추가값을 의미합니다.

BFS 너비우선탐색 구현 메서드입니다. [[String]] 타입의 이차원배열 변수에 바로 접근해서 사용할 수 있도록 extension Array에 정의해두었습니다. 탐색 시작지 x, y를 받아서 너비우선탐색을 시작합니다.

9 ~ 10행) 원본 이차원배열을 tRoom에 복사해줍니다. tRoom은 이미 탐색한 위치임을 기록하기 위해 var로 정의해서 사용합니다. 처음 시작지는 "P" 인 경우에만 탐색합니다. 중복탐색을 방지하기 위해 사전에 tRoom[x][y]의 값을 "X" 값으로 변경해줍니다.
11행) queue의 첫 탐색값을 미리 정의해서 선언합닌다. dist가 0부터 시작하도록 해서 맨해튼거리가 2이하인 경우까지만 탐색합니다. 2보다 긴 거리는 굳이 탐색할 필요가 없기 때문입니다. 우리는 초기 x, y 좌표를 기준으로 맨해튼거리를 준수하지 않는 응시자가 있는지만 확인하면 됩니다.

13 ~ 29행) 이제 초기 x, y좌표를 기준으로 하여 BFS탐색을 수행합니다. 맨해튼 거리를 준수하지 않는 응시자가 발견되면 즉시 false를 반환하고 탐색을 종료합니다. 21행에서는 다음 탐색하는 좌표가 맵 범위 (5x5)를 벗어나는 경우, 이미 탐색한 위치인경우에는 탐색하지 않도록 continue를 수행하고 있습니다. 또한 맨해튼거리가 아직 탐색이 필요한 범위인 경우에만 queue에 다음 노드를 추가하여 너비탐색을 진행합니다. 너비탐색을 수행했을때 거리두기를 제대로 실천하고 있다면, 29행에서 true를 반환합니다.

각 [String]타입의 room 맵마다 거리두기를 실천하고 있는지를 확인할때 사용하는 메서드입니다.
35행) 첨자접근을 용이하게 하기위해 [String]타입의 room을 [["P", "X", "X", ...], ["X", "P", ...]]같은 포맷의 값을 가진 5x5 크기의 [[String]] 타입으로 변환해서 BFS를 수행할 준비를 합니다.
39 ~ 45행) 응시자가 있는 위치에 한해서 BFS를 수행, 만약 거리두기를 실천하지 않는 응시자가 한명이라도 발견 되면 즉시 false를 반환해서 문제가 있는 room임을 알려줍니다.

사실 room을 [[String]]타입이 아닌, [[Character]] 타입으로 정의해서 문제를 풀어도 됩니다. 캡쳐화면과 달리 최하단 전체 소스코드는 [[Character]] 타입으로 푼 소스코드를 공유해뒀습니다. 관련해서 의견 환영합니다.

50행) 드디어 solution 메서드입니다. 여러개의 [String]타입 맵을 갖는 [[String]]타입의 places를 인자로 받습니다.
51 ~ 53행) places배열에 reduce 연산자를 사용하여 각각의 맵의 거리두기 실천여부를 확인하고, 실천하는 경우 1 / 실천하지 않는 경우 0을 누적시킨 [Int]타입의 배열을 반환합니다. 이렇게 거리두기 확인하기 문제를 풀 수 있었습니다.

언제든 의견 환영합니다. 아래는 최종 제출코드 및 전체 소스코드입니다.

---

카카오인턴십 기출, 거리두기 확인하기 swift 풀이결과 및 전체소스코드

import Foundation 

typealias Tuple = (x: Int, y: Int, dist: Int)
let dx = [0, 0, -1, 1]
let dy = [1, -1, 0, 0]

extension Array where Element == [Character] {
    func BFS(_ x: Int, _ y: Int) -> Bool {
        var tRoom = self
        tRoom[x][y] = "X"
        var queue: [Tuple] = [(x, y, 0)]
        var cur = 0
        while cur < queue.count {
            let nowPos = (x: queue[cur].x, y: queue[cur].y)
            let dist = queue[cur].dist
            cur += 1
            for ddx in dx.indices {
                let nX = nowPos.x + dx[ddx]
                let nY = nowPos.y + dy[ddx]
                if nX < 0 || nX >= 5 || nY < 0 || nY >= 5
                || tRoom[nX][nY] == "X" { continue }
                if tRoom[nX][nY] == "P" { return false }
                tRoom[nX][nY] = "X"
                if dist + 1 < 2 {
                    queue.append((nX, nY, dist + 1))
                }
            }
        }
        return true
    }
}

extension Array where Element == String {
    func isGoodRoom() -> Bool {
        let room = self.reduce(into: [[Character]]()) { (result, string) in
            let array = [Character](string)
            result.append(array)
        }
        for x in room.indices {
            for y in room[x].indices {
                if room[x][y] == "P" && !room.BFS(x, y) {
                    return false
                }
            }
        }
        return true
    }    
}

func solution(_ places:[[String]]) -> [Int] {
    return places.reduce(into: [Int]()) { (answer, room) in
        answer.append(room.isGoodRoom() ? 1 : 0)
    }
}