https://school.programmers.co.kr/learn/courses/30/lessons/81302
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
Code
class Solution {
fun solution(places: Array<Array<String>>): IntArray {
var answer: IntArray = intArrayOf()
for (place in places){
val room = arrayOf(place[0].split(""), place[1].split(""),place[2].split(""),place[3].split(""),place[4].split(""))
println(room.toList().toString())
answer = answer.plus(checkPlace(room))
}
return answer
}
fun checkPlace(room: Array<List<String>>): Int{
println()
for (i in 0 until 5){
for (j in 1 .. 5){
print(room.get(i).get(j))
if (room.get(i).get(j) == "P") if (atP(i,j,room)) return 0
if (room.get(i).get(j) == "O") if(atO(i,j,room)) return 0
}
println()
}
return 1
}
fun checkX(num: Int): Boolean = num < 5 && num >= 0
fun checkY(num: Int): Boolean = num < 6 && num >= 1
fun isP(x: Int, y: Int, room: Array<List<String>>): Boolean = room.get(x).get(y) == "P"
fun atP(x: Int, y: Int, room: Array<List<String>>): Boolean{ // 사람 옆이니까 사람이 한명도 존재하면 안됨. return 0
val left = y - 1
val right = y + 1
val up = x + 1
val down = x - 1
if (checkY(left))
if (isP(x,left,room)) return true
if (checkY(right))
if (isP(x,right,room)) return true
if (checkX(up))
if (isP(up,y,room)) return true
if (checkX(down))
if (isP(down,y,room)) return true
return false
}
fun atO(x: Int, y: Int, room: Array<List<String>>): Boolean { // 빈테이블 옆이니까 사람이 두명이상 존재하면 안됨. return 0
var cnt = 0
val left = y - 1
val right = y + 1
val up = x + 1
val down = x - 1
if (checkY(left))
if (isP(x,left,room)) cnt++
if (checkY(right))
if (isP(x,right,room)) cnt++
if (checkX(up))
if (isP(up,y,room)) cnt++
if (checkX(down))
if (isP(down,y,room)) cnt++
if (cnt >= 2) return true
return false
}
}풀이
사실 이번 문제는 흔히들 말하는 정석과는 다른 방식으로 풀었다. DFS 혹은 BFS와 같은 그래프 탐색 기법을 활용해서 문제를 해결한 경우가 대부분이다. 내 풀이는 굳이 따지자면 완전탐색 혹은 브루트 포스라고 생각한다.
문제에 대해서 간단하게 설명을 하자면
place에 존재할 수 있는 타입은 3가지. 사람(P), 테이블(O), 파티션(X)이다.
맨해튼 거리가 2라는 것은 사람 하나를 둘러싼 곳에서 또다른 사람이 존재하냐를 묻는 것이다. 즉 본인을 기준으로 상하좌우 2칸, 대각선 1칸 이내에 다른 사람이 있는지 검사하는 것이다.
?
? ? ?
? ? P ? ?
? ? ?
?
이때, 조건이 하나 있다. 맨해튼 거리에 사람이 존재하더라도 파티션으로 막고있으면 상관이 없다.
?
P X ?
? X P X P
? ? ?
?
이런식의 상황도 허용이 된다는 것이다.
처음 생각에 제한사항들을 전부다 조건으로 넣는다면 너무 비효율적인 코드가 나올것 같았다. 그래서 생각을 바꿔보았다. 그럼 허용이 안되는 즉, 0을 return하는 상황은 어떤걸까?
P P P => 사람이 연속으로 있는 경우(좌, 우, 상, 하 전부)
P O P => 사람과 사람 사이에 테이블이 있는 경우
? P
P O => 사람과 사람이 대각선일때, 그 가운데에 테이블이 있는 경우
이러한 경우들이 나왔다.
이 그림을 자세히 보다보면 규칙이 나온다.
1. P의 상하좌우에 P가 하나라도 존재할 경우 허용이 되지 않는다.
2. O의 상하좌우에 P가 두개이상 존재할 경우 혀용이 되지 않는다.
그럼 파티션으로 막고있는 경우도 있지않냐. 생각할수도 있다.
? P
P X
이런 상황일 경우 ?의 값이 X라면 파티션이 막고있으니 허용이 되지만, O혹은 P라면 허용이 되지 않는 상황이다.
즉, 파티션이 막고있더라도 해당 부분이 허용이 되지 않는 상황을 만들려면 결국 P혹은 O에 의해서 P가 연결되는 상황이 나온다.
그렇기 때문에 P의 상하좌우에 P가 하나라도 존재한다면 0을 반환하여 array에 넣어주고,
O의 상하좌우에 P가 두개이상 존재한다면 0을 반환하여 array에 넣어주면 된다.
그게 아닐경우 1을 반환해서 넣어준다.
checkX와 checkY의 경우 값이 범위를 벗어나지 않았는지 확인하는 용도이다. 5x5 범위를 벗어난 즉, -1 or 6 index에 접근하는 경우를 막아준다. 하지만 자세히 보면 checkX와 checkY의 범위를 다르게 설정해뒀다. split으로 한칸씩 떼어냈더니 ["", "P", "P", "O", "X", "P", ""]와 같이 필요없는 값이 좌우로 하나씩 생겼는데 왜 그런질 모르겠어서 범위를 늘리는 방식으로 해결했다.
이후는 간단하다.
모든 칸을 순회하며 현재칸을 확인한다.
P일경우 상하좌우 값을 활용해서 범위를 벗어나지 않았는지 확인하고, 벗어나지 않았다면 상하좌우에 P가 존재하는지 검사한다. P가 한번이라도 나왔다면 0을 결과에 넣어준다.
O일 경우 상하좌우 값을 활용해서 범위를 벗어나지 않았는지 확인하고, 벗어나지 않았다면 상하좌우에 P가 존재하는지 검사한다. P가 두번이상 나왔다면 0을 결과에 넣어준다.
생각보다는 간단한 방식으로 풀 수 있는 문제였다. 하지만, 누가봐도 그래프인 문제를 상하좌우만 확인해서 해결할 수 있다는 아이디어를 떠올리는게 어려웠던 문제다. 문제를 풀때는 정해진 풀이로 정석적으로 푸는것도 좋다. 하지만 이렇게 더 간단한 방법이 있는지 떠올리고, 활용하는 방법이 더 좋다고 생각한다. 자유로운 사고가 유연한 문제 풀이를 만들어 준다.