문제 링크

문제 풀이 아이디어

places의 길이가 최대 5이고 place는 각각 5 * 5의 행렬입니다. 따라서 완전탐색을 해도 125번의 연산 밖에 하지 않습니다. 시간 복잡도에 대해서는 걱정할 필요가 없습니다.

두 “P” 지점에 대해서 맨해튼 거리 2 이하의 좌표를 탐색해서 다른 “P”가 있는지 확인하고 “P”가 있다면 사이에 파티션이 있는지 확인하는 방법을 사용해보겠습니다.

“P” 지점이 빨간 점이라고 한다면 맨해튼 거리 2 이하의 좌표는 노란색을 칠한 부분과 같습니다. 하지만 노란색 부분만 탐색하는 것은 코드로 구현하기 쉽지 않으므로 상하좌우 +/- 2의 영역을 모두 탐색하면서 맨해튼 거리 2 이하인 부분만 “P”가 있는지 확인해보도록 하겠습니다.

처음 풀이 코드

struct Position: Equatable {
    let r: Int
    let c: Int
}

func isDistanced(_ place: [[String]], _ p: Position) -> Bool {

    // 해당 좌표가 5 x 5 행렬 안에 있는지 확인하는 함수 (index out of bound 방지)
    func isValid(_ p: Position) -> Bool {
        (0...4).contains(p.r) && (0...4).contains(p.c)
    }

    // 맨해튼 거리를 구하는 함수
    func manDistance(_ p1: Position, _ p2: Position) -> Int {
        abs(p1.r - p2.r) + abs(p1.c - p2.c)
    }

    // 맨해튼 거리가 2이하인 두 지점 사이에 파티션이 있는지 구하는 함수
    func isParted(_ p1: Position, _ p2: Position) -> Bool {
        // 같은 행에 있는 경우
        if p1.r == p2.r {
            return place[p1.r][(p1.c + p2.c) / 2] == "X"
        // 같은 열에 있는 경우
        } else if p1.c == p2.c {
            return place[(p1.r + p2.r) / 2][p1.c] == "X"
        // 대각선으로 있는 경우 (파티션 2개 필요)
        } else {
            return place[p1.r][p2.c] == "X" && place[p2.r][p1.c] == "X"
        }

    }

    // 상하좌우로 2거리만큼 완전탐색
    for i in (-2...2) {
        for j in (-2...2) {
            let np = Position(r: p.r + i, c: p.c + j)
            // 같은 좌표 or 유효하지 않은 좌표 or 해당 좌표에 사람이 없는 경우
            if (p == np) || !isValid(np) || place[np.r][np.c] != "P" {
                continue
            // 해당 위치가 맨해튼 거리 2보다 크거나, 이미 파티션이 있는 경우
            } else if manDistance(p, np) > 2 || isParted(p, np)  {
                continue
            // 그렇지 않은 경우 (= 거리두기를 지키지 않은 경우)
            } else {
                return false
            }
        }
    }

    return true
}

func solution(_ places:[[String]]) -> [Int] {
    
    // [[String]]을 subscript를 사용하기 좋게 [[[String]]]으로 바꿈
    let places = places.map { $0.map { $0.map { String($0) } } }
    var ans = [Int]()

    // 모든 place를 탐색
    for place in places {
        var flag = true
        // 5 x 5 행렬을 탐색
        Outerloop: for r in 0..<5 {
            for c in 0..<5 {
                // 거리두기를 지키지 않은 경우
                if place[r][c] == "P" && !isDistanced(place, Position(r: r, c: c)) {
                    flag = false
                    break Outerloop
                }
            }
        }
        ans.append(flag ? 1 : 0)
    }

    return ans
}

개선된 코드

좀 더 짧고 빠른 풀이입니다. 5 x 5를 완전탐색하면서 일단 “P”의 좌표를 찾습니다. 그 후 “P”의 좌표가 서로서로 맨해튼 거리가 2보다 큰지, 만약에 2보다 작다면 사이에 파티션이 위치하는지 확인하는 방법입니다.

“P”를 만날 때마다 25번의 연산을 해야하는 위 풀이보다 더 간결한 것 같습니다. 다만 연산량이 적기 때문에 실행 시간에 있어서 의미있는 차이가 나지는 않습니다.

struct Position: Equatable {
    let r: Int
    let c: Int
}

func isDistanced(_ place: [[String]]) -> Bool {
    
    // 사람 좌표 배열
    var persons = [Position]()
    
    // 완전탐색해서 사람 좌표 구하기
    for r in 0..<5 {
        for c in 0..<5 {
            if place[r][c] == "P" {
                persons.append(Position(r: r, c: c))
            }
        }
    }

    // 맨해튼 거리를 구하는 함수
    func manDistance(_ p1: Position, _ p2: Position) -> Int {
        abs(p1.r - p2.r) + abs(p1.c - p2.c)
    }

    // 맨해튼 거리가 2이하인 두 지점 사이에 파티션이 있는지 구하는 함수
    func isParted(_ p1: Position, _ p2: Position) -> Bool {
        // 같은 행에 있는 경우
        if p1.r == p2.r {
            return place[p1.r][(p1.c + p2.c) / 2] == "X"
        // 같은 열에 있는 경우
        } else if p1.c == p2.c {
            return place[(p1.r + p2.r) / 2][p1.c] == "X"
        // 대각선으로 있는 경우 (파티션 2개 필요)
        } else {
            return place[p1.r][p2.c] == "X" && place[p2.r][p1.c] == "X"
        }

    }

    for p1 in persons {
        for p2 in persons {
            // 동일한 좌표이거나 맨해튼 거리가 2보다 큰 경우
            if p1 == p2 || manDistance(p1, p2) > 2 {
                continue
            // 맨해튼 거리가 1인 경우 (= 파티션 칠 수 없음)
            } else if manDistance(p1, p2) == 1 {
                return false
            // 맨해튼 거리가 2인데 파티션이 없는 경우
            } else if !isParted(p1, p2) {
                return false
            }
        }
    }
    

    return true
}

func solution(_ places:[[String]]) -> [Int] {
    
    // [[String]]을 subscript를 사용하기 좋게 [[[String]]]으로 바꿈
    let places = places.map { $0.map { $0.map { String($0) } } }
    var ans = [Int]()

    // 모든 place를 탐색
    for place in places {
        ans.append(isDistanced(place) ? 1 : 0)
    }

    return ans
}