문제
풀이 언어
Kotlin
코드
import java.util.*
class Solution {
fun solution(places: Array<Array<String>>): IntArray {
val answer = mutableListOf<Int>()
val size = places.size
for (place in places) {
var check = 0
for (i in 0 until size) {
for (j in 0 until size) {
if (place[i][j] == 'P') {
if (bfs(place, i, j, size).not()) {
check = 1
break
}
}
}
if (check == 1) {
break
}
}
if (check == 1) answer.add(0)
else answer.add(1)
}
return answer.toIntArray()
}
fun bfs(place: Array<String>, src_x: Int, src_y: Int, size: Int): Boolean {
val queue = LinkedList<Array<Int>>()
var visited = Array(size) { IntArray(size) { 0 } }
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
queue.add(arrayOf(src_x, src_y, 0)) // x, y, 거리
visited[src_x][src_y] = 1
while (queue.isNotEmpty()) {
val element = queue.poll()
val x = element[0]
val y = element[1]
val dist = element[2]
if (dist >= 3) return true
else if (dist != 0 && place[x][y] == 'P') return false
for (i in 0..3) {
val nx = x + dx[i]
val ny = y + dy[i]
val nd = dist + 1
if (nx in 0 until size && ny in 0 until size) {
if (place[nx][ny] != 'X' && visited[nx][ny] == 0) {
queue.add(arrayOf(nx, ny, nd))
visited[nx][ny] = 1 // 해당지점 방문
}
}
}
}
return true
}
}
풀이 방법
면접자가 앉아 있는 곳에서 BFS
를 진행한다. 이 때 거리가 3보다 크거나 같은 경우 거리두기
가 제대로 되어 있는 상태이므로 true
를 리턴한다. 거리가 3보다 작고 해당 좌표에 면접자가 앉아 있는 경우 거리두기
가 제대로 되어 있지 않은 상태이므로 false
를 리턴한다. 두 가지 조건에 해당하지 않는 경우에는 다음 이동할 좌표를 탐색한다.
결과
'✍️ 코테 준비 > DFS, BFS' 카테고리의 다른 글
[DFS와 BFS] [Python / C++] 1260. DFS와 BFS (0) | 2021.04.18 |
---|---|
[DFS와 BFS] [Python / C++] 1707. 이분 그래프 (0) | 2021.04.14 |
[DFS와 BFS] [Python / C++] 7562. 나이트의 이동. (0) | 2021.04.13 |
[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기. (0) | 2021.04.12 |