[Swift 알고리즘] 프로그래머스(Lv.2) - 거리두기 확인하기( 4월 25일 테케 추가) / 2021 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 거리두기 확인하기" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 그래프 탐색 문제입니다. (아마..?)

저는 이 문제에서 풀면서도 이게 맞나? 멈칫하는데 시간을 더 쓴 거 같습니다.

이번 문제는 5x5의 배열이 5개가 들어온다고 고정되어 있으므로 반복 횟수는 상수 5로 적었습니다.

 

강의실 1개에 대해 알고리즘을 실행합니다.

 

1. 강의실 1개의 위치 배열을 만듭니다.

이번 문제는 특이하게 1차원 배열에 2차원 배열 형태의 input이 들어온다는 것입니다.

그래서 1차원 배열을 2차원 배열로 변환하는 과정이 필요했습니다.

 

2. 강의실 안의 사람 좌표를 구합니다.

튜플을 이용하여 x, y 좌표를 저장했습니다. 코드에서는 x가 y 좌표이고 y가 x 좌표입니다.

 

2-1. 사람이 없는 경우에 대한 예외 처리를 합니다.

사람이 없으면 거리두기를 지킨 것으로 간주합니다. (문제 예시 참고)

 

3. dfs로 사람과 사람 사이의 거리를 측정합니다.

A, B, C라는 사람이 있다면 A-B, A-C / B-A, B-C / C-A, C-B 의 거리를 측정합니다.

input의 범위가 컸다면 이미 측정한 사람은 다시 재지 않는 최적화가 필수일 것 같습니다.

 

4. 상하좌우를 1칸씩 이동하며 거리를 측정합니다.

4-1. "O"를 만나면 바로 이동합니다.

4-2. "X"를 만나면 이동하지 못합니다.

4-3. "P"를 만나면 거리를 측정합니다.

• 거리가 2 초과면 거리두기를 지킨 것입니다.
• 거리가 2 이하면 파티션이 있는지 확인합니다.
  • 두 사람이 같은 세로축에 존재하면 두 사람 사이의 세로 범위 내에 파티션이 있어야 합니다.
  • 두 사람이 같은 가로축에 존재하면 두 사람 사이의 가로 범위 내에 파티션이 있어야 합니다.
  • 두 사람이 대각선이라면 가로 세로 모두 파티션이 있어야 합니다.

5. 거리두기를 지켰는지 results 배열에 append 합니다.

 

+ 4월 25일 테케 추가

2022년 4월 25일에 테스트 케이스가 추가되었습니다.

제 기존 코드는 31번 테스트 케이스를 통과를 하지 못했습니다.

다음 노드를 추가할 때 거리가 2 이하인 노드만 확인, 추가하였더니 통과하였습니다.

혹시 헤매고 있으신 분은 참고하시면 좋겠습니다.

 

후기

구현에 가까운 문제라 이게 맞는 풀이인가 풀면서도 아리송 했습니다.

확신이 있었다면 30분 안에 풀었겠지만 아닌거 같은데..? ㅠㅠ 하는 생각에 1시간 30분정도 소요가 됐습니다.

더 연습을 해야겠습니다.

 

감사합니다!

---

전체 코드

//2시간 55분 시작
// 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면,
// T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 
import Foundation

let person = "P"
let partition = "X"
let size = 5

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

func checkPartition(_ classroom: [[String]], a: (Int, Int), b: (Int, Int)) -> Bool {
    if a.0 == b.0 { //같은 행이라면 세로 사이에 파티션이 있어야 한다.
        return (classroom[a.0][(a.1+b.1)/2] == partition)
    } else if a.1 == b.1 { //같은 열이라면 가로 사이에 파티션이 있어야 한다.
        return (classroom[(a.0+b.0)/2][a.1] == partition)
    } else { //대각선이라면 위아래로 파티션이 모두 있어야 한다.
        return classroom[a.0][(a.1+b.1)/2] == partition && classroom[(a.0+b.0)/2][a.1] == partition 
    }
}

func checkDistance(_ classroom: [[String]], start: (Int, Int)) -> Bool {
    let dx: [Int] = [-1, 1, 0, 0]
    let dy: [Int] = [0, 0, -1, 1]

    var queue: [(Int, Int)] = [start]
    var index = 0
    var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: size), count: size)
    visited[start.0][start.1] = true
    
    while index < queue.count {
        let node = queue[index]
        index += 1
        
        for i in 0..<4 {
            let nx = node.0 + dx[i]
            let ny = node.1 + dy[i]
                
            guard (0..<size) ~= nx, (0..<size) ~= ny else { continue }
            
            let distance = abs(nx - start.0) + abs(ny - start.1)
            guard distance <= 2 else { continue }
            
            guard !visited[nx][ny] else { continue }
            visited[nx][ny] = true 
                        
            if classroom[nx][ny] == person {
                if distance <= 1 {
                    return false
                } else if distance == 2 { //맨해튼 거리가 2 이상이면 OK
                    //맨해튼 거리가 2 이하일 때 파티션을 체크한다.
                    if !checkPartition(classroom, a: start, b: (nx, ny)) { //파티션이 없으면 false
                        return false    
                    }
                }
            } else if classroom[nx][ny] == "O" {
                queue.append((nx, ny))    
            }
        }
    }
    
    return true
}

func solution(_ places:[[String]]) -> [Int] {    
    var result: [Int] = []

    for place in places {
        //강의실 하나를 의미하는 2차원 배열을 만든다
        let classroom = splitClassroom(place)
        var resultInt = 1
        
        for i in 0..<size {
            guard resultInt == 1 else { break }
            
            for j in 0..<size {
                //하나하나 탐색하면서 응시자를 만나면 다른 응시자와 맨해튼 거리를 측정한다.
                if classroom[i][j] == person {
                    //bfs를 이용해 거리 체크
                    if !checkDistance(classroom, start: (i, j)) {
                        resultInt = 0
                        break
                    }
                }
            }
        }
        
        result.append(resultInt)
    }
    
    return result
}

 

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.