프로그래머스 - 거리두기 확인하기

문제

[https://school.programmers.co.kr/learn/courses/30/lessons/81302]

접근법

각 배열의 P마다 거리 차이가 1,2인 주변을 조사해서 P가 있는 경우를 조사하면 되는데

1. 거리가 1일 경우 -> 이때는 무조건 지켜지지 않음
2. 거리가 2일 경우 -> 대각선으로 위치해있거나 같은 행/열에서 2칸 차이 날 때

거리가 2일 경우에는 몇가지 경우를 생각해 봐야 하는데
PX
XP

• 이런식으로 대각선으로 위치해 있을 때 칸막이가 두개 있다면 거리두기가 지켜지고

• PXP 같이 같은 행/열에서 두 칸 차이나는 곳에 위치해 있다면, 그 사이에 칸막이가 있으면 거리두기가 지켜짐

대각선 조사

여기서 조금 헷갈렸던게 P가 대각선으로 위치해 있는 경우, 인근에 X가 위치해 있는지를 조사해야 하는데 그 위치를 어떻게 알아야 하는지가 헷갈렸는데

Ex) (0,0)과 (1,1)에 P가 있을 때 -> (0,1)과 (1,0)에 X가 있는지를 조사해야 하는데 이 값은 어떻게 나와야 하는지?

괜히 어렵게 생각했는데 찾고보니까
내가 찾은 P의 좌표값을 (x,y) , 대각선에 위치해 있는 P를 (nextX,nextY)라고 놓고

const [xdiff,ydiff] = [nextX-x,nextY-y]
=> place[x+xdiff][y] , place[x][y+ydiff]

그런데... x+nextX-x == nextX이기 때문에....

현재 P의 좌표 하나는 고정해놓고 하나는 대각선에 위치한 P의 좌표로 바꿔주면 됨

place[nextX][y]], place[x][nextY]

같은 행/열에서 2칸 조사

이 경우에는 현재 좌표+2칸 차이나는 좌표 / 2 해주면 됨

Ex) (0,2) (2,2) => (0+2/2),(2+2/2) => (1,2)

이렇게 총 3가지를 조사해서 만약 하나라도 안맞는다면 그 대기실 전체는 거리두기가 지켜지지 않게 됨

요약해보면

1. 각 대기실에서 P의 위치를 찾음
2. P와 한 칸 차이나는 곳을 조사해서 P가 있으면 -> 거리두기 X
3. p와 대각선으로 두 칸 차이나는 곳을 조사해서 p가 있으면 -> place[nextX][y] 와 place[x][nextY]가 둘다 X가 아니라면 -> 거리두기 X
4. p와 같은 행/열 안에서 두 칸 차이나는 곳을 조사해서 p가 있으면 -> 그 사이가 X가 아니라면 -> 거리두기 X
5. 하나라도 거리두기가 X면 그 대기실은 0 리턴

코드

function solution(places) {
   //p한테 1거리에 P 또 있으면 - 안됨
   //p한테 2거리에 P 또 있으면 - 조사
   const xMax = 5
   const yMax = 5
   const dirs = [[-1,0],[0,-1],[1,0],[0,1]]
   const diagonals = [[-1,-1],[1,1],[1,-1],[-1,1]]
   const aparts = [[0,-2],[0,2],[2,0],[-2,0]]
   const bfs = (row,col,place) => {
      for(let dir of dirs){//거리 1일 때
          const [nextX,nextY] = [row+dir[0],col+dir[1]]
          if(nextX < 0 || nextX >=  xMax || nextY < 0 || nextY >= yMax){
              continue
          }
          if(place[nextX][nextY] === 'P'){
              return false
        }
   }
      for(let diagonal of diagonals){//대각선으로 앉아있을 때
          const [nextX,nextY] = [row+diagonal[0],col+diagonal[1]]
          if(nextX < 0 || nextX >=  xMax || nextY < 0 || nextY >= yMax){
              continue
          }
          if(place[nextX][nextY] === 'P'){//대각선
              const [xdiff,ydiff] = [nextX-row,nextY-col]
              if(place[nextX][col] !=='X' || place[row][nextY] !== 'X'){return false}
          }
      }
      for(let apart of aparts){//같은줄 거리 2일때
          const [nextX,nextY] = [row+apart[0],col+apart[1]]
          if(nextX < 0 || nextX >=  xMax || nextY < 0 || nextY >= yMax){
              continue
          }
          if(place[nextX][nextY] === 'P'){
             const [xMiddle,yMiddle] = [(nextX+row)/2 , (nextY+col)/2]
            if(place[xMiddle][yMiddle] ==='O'){
                return false
            }
          }
      }
       return true
   }
   return places.map((place) => {
       let a = true
       for(let row=0;row<xMax;row++){
           for(let col=0;col<yMax;col++){
               if(place[row][col] === 'P'){
              if(!bfs(row,col,place)){return 0}
               }
           }
       }
       return a ? 1 : 0})
}