1️⃣ 문제

문제 - 카카오 거리두기 확인하기

풀이 참조 - Youtube

P를 기준으로 bfs로 접근하여 확인하면 된다는 아이디어만 가진 채, 그래프를 만들어 풀려고 했었는데, 오히려 더 복잡해지고 어려워지니까 손에서 놓게 되더라,,, 그래서 알고리즘 손놓으니까 감도 떨어지고 ,,,ㅎ 와중에 파이썬 풀이긴 하지만 꼼꼼이 설명을 잘해주는 유툽을 찾아서 참고하여 swift로 내가 다시 풀었다@~@!!

2️⃣ 풀이 방법 및 코드

1️⃣ 구간(?) 정해주기

맨해튼 거리를 측정하기 때문에, 해당 칸에서 이동할 수 있는 방법은 상하좌우만 된다.(대각선 X)

그래서 이동할 수 있는 경우의 x, y 이동 벡터를 D에 [[Int]]로 저장

모든 대기실은 5x5라서 for문 또는 유효한 새로운 자리에 접근하기 용이하게 따로 저장했다.

let D = [[-1, 0], [1,0], [0, -1], [0, 1]]   // 상, 하, 좌, 우
let range = 0..<5

2️⃣ Solution 함수

대기실들에 대하여 하나씩 접근하면서 Bool을 반환하는 check 함수로 거리두기를 잘 지키는 지 체크함

  • 지켰다면 1을, 못지켰다면 0을 answer 배열에 append
func solution(_ places:[[String]]) -> [Int] {
    var answer = [Int]()
    
    places.forEach {
        if check($0) {
            answer.append(1)
        } else {
            answer.append(0)
        }
    }
    return answer
}

3️⃣ 거리두기가 잘 지켜졌는지 확인하는 check 함수

  1. ["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"] 형태의 [String] 배열을 한 자리 한 자리 접근할 수 있게 map 함수를 이용하여 문자 하나하나 끊어서 [String]으로 만들어주기
    • like [[“P”, “O”, “O”, …], […] , […, “X”, “X”, “P”]]
    • 이렇게 만들어야 String.Index를 쓰지 않고 Array[row][col]로 편하게 대기실 자리에 접근할 수 있음!
  2. 1에서 만든 [[String]]에 순서대로 접근하면서 사람인 P가 나올 때마다 bfs 함수로 맨해튼을 지키는지 확인한다.
    • false 나오면 못 지키는 경우를 찾은 것
    • 대기실 모든 자리에 접근했는데도 false가 거리두기가 잘 지켜진 것이기 때문에 true를 반환
func check(_ place: [String]) -> Bool {
  	// 1
    let placeArray = place.map { $0.map { String($0) }}
    
  	// 2  
    for r in range {
        for c in range {
            if placeArray[r][c] == "P" {
                if bfs(placeArray, r, c) == false {
                    return false
                }
            }
        }
    }
    return true
}

4️⃣ 맨해튼 거리를 지켰는지 확인할 bfs 함수

  1. 자리를 방문했는지를 기록할 visited와 bfs를 위한 큐를 만들고, 사람이 있는 첫 자리를 방문 여부는 true로 해주고 큐에 enqueue 한다.
    • 큐의 형태는 (row, col, depth)
  2. 큐를 통한 본격 bfs 탐색
    1. 큐의 첫번째 원소 dequeue하여 현재 위치인 curr에 저장하고, depth가 2를 넘으면 continue, depth가 0이 아닌데 해당 자리에 사람이 있다면 false return하기(거리두기가 안된 것!)
    2. 이 구간까지 왔다면 거리두기 문제 없는 경우이기 때문에 다른 자리로 탐색 이동해야 한다. D를 통해 상하좌우 한번씩 접근하게 됨
      1. 해당 방향 벡터를 현재 위치에 가감하여 새로운 자리의 row, col을 저장해준다.
      2. 새로 저장한 자리가 5x5 범위 내에 있고, 방문한 적이 없는지 확인한다. (범위 밖 또는 방문 했다면 continue)
      3. 다음 자리가 파티션이 있다면, 또 그 다음 자리에 사람이 있어도 거리두기를 지키는 것이기 때문에 더 탐색할 필요 X, 그래서 continue 해주기
      4. 다음 자리를 방문한 것으로 바꿔주고, 큐에 enqueue
func bfs(_ place: [[String]], _ row: Int, _ col: Int) -> Bool {
		// 1
    var visited = Array(repeating: Array(repeating: false, count: 5), count: 5)
    var q = [[Int]]()
    visited[row][col] = true
    q.append([row, col, 0]) // 마지막 원소는 depth
  
    // 2
    while !q.isEmpty {
        // 2.1
      	let curr = q.removeFirst()
        
        if curr[2] > 2 {
            continue
        }
        if curr[2] != 0 && place[curr[0]][curr[1]] == "P" {  // 거리두기 안지켜짐
            return false
        }
        
        // 2.2 네 방향 체크
        for d in D {
          // 2.2.1
          let nextRow = curr[0] + d.first!
          let nextCol = curr[1] + d.last!
            
          // 2.2.2
          guard range.contains(nextRow) && range.contains(nextCol) else { continue }
          guard !visited[nextRow][nextCol] else { continue }
            
          // 2.2.3
          if place[nextRow][nextCol] == "X" {
            continue
          }
          // 2.2.4
          visited[nextRow][nextCol] = true
          q.append([nextRow, nextCol, curr[2] + 1])
        }
    }
    return true
}

3️⃣ 이 문제를 풀면서 되새긴 점

bfs 너무 어렵게 생각하지 말자!!! 쫄지말자 🤨