🔎 거리두기 확인하기

❓ 문제링크

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

📄 제출 코드

// 맨허튼 거리 |x2-x1| + |y2-y1|
// 맨허튼거리 2이하로앉지말기

// P : 사람
// O : 빈자리
// X : 파티션
// 사이에 파티션이 있다면 ok PXP

// 아래 경우도 지킨것
// XP
// PX

// 아래는 지키지 않은 것
// XP
// OP
function solution(places) {
  var answer = [];
  // let map = makeMap(places);
  
  for (let t = 0; t < 5; t++) {
    let map = places[t];
    let flag = true;
    for (let i = 0; i < 5; i++) {
      for (let j = 0; j < 5; j++) {
        if (map[i][j] == 'P') {
          if (isValid(i+1, j) && map[i + 1][j] == 'P') flag = false;
          if (isValid(i, j+1) && map[i][j+1] == 'P') flag = false;
          if (isValid(i+2, j) && map[i + 2][j] == 'P' && map[i+1][j] != 'X') flag = false;
          if (isValid(i, j+2) && map[i][j + 2] == 'P' && map[i][j+1] != 'X') flag = false;
          if (isValid(i+1, j+1) && map[i + 1][j + 1] == 'P' && (map[i][j+1] != 'X' || map[i+1][j]!='X')) flag = false;
          if (isValid(i-1, j+1) && map[i - 1][j + 1] == 'P'&& (map[i][j+1] != 'X' || map[i-1][j]!='X')) flag = false;
        }
      }
    }

    flag ? answer.push(1) : answer.push(0)
  }
  return answer;
}
function isValid(x, y) {
  if (x >= 0 && y >= 0 && x < 5 && y < 5) return true;
  return false;
}

let places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]];
console.log(solution(places));

처음엔 bfs로 계산하면서 풀려고 했었다.
그러나 bfs를 돌때 대각선의 경우를 어떻게 생각하지 한참 고민하다가 bfs할 필요 없이 안되는 경우만 생각하면 되지 않을까라는 생각이 들었다.

P : 사람, O : 빈공간, X : 파티션
(자꾸 P가 파티션이라고 착각해서 적어놓고 시작.)

거리두기를 지키는 경우

• 맨허튼 거리가 2보다 경우
• PXP
• XP
  PX

안되는 경우

1. 아래 한칸이 P인 경우
2. 우측 한칸이 P인 경우
   // 1자 경우 (POP)
3. 두칸 아래가 P이지만, 한칸 아래가 X가 아닌경우
4. 두칸 우측이 P이지만, 한칸 우측이 X가 아닌경우
   // 사각형 경우
5. 대각선 한칸 아래가 P이고, 한칸 아래가 X가 아니거나 한칸 우측이 X가 아닌경우
6. 대각선 한칸 위가 P이고, 한칸 위가 X가 아니거나 한칸 우측이 X가 아닌경우

구현은 places를 돌면서 P인경우 위의 6조건중 하나라도 만족하지 않으면, flag를 false로 두어 마지막에 flag가 false면 0을 넣고, true면 1을 넣었다.