1️⃣ 문제
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 함수
["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"]
형태의 [String] 배열을 한 자리 한 자리 접근할 수 있게map
함수를 이용하여 문자 하나하나 끊어서 [String]으로 만들어주기- like [[“P”, “O”, “O”, …], […] , […, “X”, “X”, “P”]]
- 이렇게 만들어야
String.Index
를 쓰지 않고Array[row][col]
로 편하게 대기실 자리에 접근할 수 있음!
- 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 함수
- 자리를 방문했는지를 기록할 visited와 bfs를 위한 큐를 만들고, 사람이 있는 첫 자리를 방문 여부는 true로 해주고 큐에 enqueue 한다.
- 큐의 형태는 (row, col, depth)
- 큐를 통한 본격 bfs 탐색
- 큐의 첫번째 원소 dequeue하여 현재 위치인 curr에 저장하고, depth가 2를 넘으면 continue, depth가 0이 아닌데 해당 자리에 사람이 있다면 false return하기(거리두기가 안된 것!)
- 이 구간까지 왔다면 거리두기 문제 없는 경우이기 때문에 다른 자리로 탐색 이동해야 한다. D를 통해 상하좌우 한번씩 접근하게 됨
- 해당 방향 벡터를 현재 위치에 가감하여 새로운 자리의 row, col을 저장해준다.
- 새로 저장한 자리가 5x5 범위 내에 있고, 방문한 적이 없는지 확인한다. (범위 밖 또는 방문 했다면 continue)
- 다음 자리가 파티션이 있다면, 또 그 다음 자리에 사람이 있어도 거리두기를 지키는 것이기 때문에 더 탐색할 필요 X, 그래서 continue 해주기
- 다음 자리를 방문한 것으로 바꿔주고, 큐에 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 너무 어렵게 생각하지 말자!!! 쫄지말자 🤨