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

문제

코딩테스트 연습 - 거리두기 확인하기

 

코드

function solution(places) {
  const w = 5;
  const h = 5;

  function checkDistance(x, y, place) {
    const [dx1, dy1] = [
      [-1, 0, 1, 0],
      [0, 1, 0, -1],
    ];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx1[i];
      const ny = y + dy1[i];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
      if (place[nx][ny] === 'P') return 0;
    }

    const [dx2, dy2] = [dx1.map((v) => 2 * v), dy1.map((v) => 2 * v)];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx2[i];
      const ny = y + dy2[i];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
      if (place[nx][ny] === 'P' && place[x + dx1[i]][y + dy1[i]] !== 'X')
        return 0;
    }

    const [dx3, dy3] = [
      [-1, 1, 1, -1],
      [1, 1, -1, -1],
    ];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx3[i];
      const ny = y + dy3[i];
      const nIdx = (i + 1) % 4;
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
      if (
        place[nx][ny] === 'P' &&
        (place[x + dx1[i]][y + dy1[i]] !== 'X' ||
          place[x + dx1[nIdx]][y + dy1[nIdx]] !== 'X')
      )
        return 0;
    }
    return 1;
  }

  return places.map((place) => {
    for (let i = 0; i < w; i++) {
      for (let j = 0; j < h; j++) {
        if (place[i][j] === 'P') {
          if (!checkDistance(i, j, place)) return 0;
        }
      }
    }
    return 1;
  });
}

---

풀이

조건을 보면, 한 응시자의 2만큼의 맨하튼 거리에는 다른 응시자가 있으면 안된다.

그러나 두 응시자 끼리의 접근이 파티션 'X' 로 막혀 있다면, 허용된다.

 

이 정보를 바탕으로, 3가지 경우를 확인한다.

 

1. 1만큼의 맨하튼 거리에 응시자가 있는가?
2. 2만큼의 맨하튼 거리에 응시자가 있는가?

 - 2.1 현재 위치로부터 대각선에 응시자가 있는가?

 - 2.2 상하좌우 2칸 거리에 응시자가 있는가?

 

그림으로 나타내보면,

매우 조잡하지만 다음과 같다.

 

이를 순서대로 검증한다.

    const [dx1, dy1] = [
      [-1, 0, 1, 0],
      [0, 1, 0, -1],
    ];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx1[i];
      const ny = y + dy1[i];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
      if (place[nx][ny] === 'P') return 0;
    }

1 맨하탄 거리에 응시자가 있다면, 거리두기를 위반했다.

 

    const [dx2, dy2] = [dx1.map((v) => 2 * v), dy1.map((v) => 2 * v)];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx2[i];
      const ny = y + dy2[i];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
      if (place[nx][ny] === 'P' && place[x + dx1[i]][y + dy1[i]] !== 'X')
        return 0;
    }

상하좌우로 2 맨하탄 거리에 응시자가 있고, 그 사이에 파티션이 없다면 거리두기를 위반했다.

 

    const [dx3, dy3] = [
      [-1, 1, 1, -1],
      [1, 1, -1, -1],
    ];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx3[i];
      const ny = y + dy3[i];
      const nIdx = (i + 1) % 4;
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
      if (
        place[nx][ny] === 'P' &&
        (place[x + dx1[i]][y + dy1[i]] !== 'X' ||
          place[x + dx1[nIdx]][y + dy1[nIdx]] !== 'X')
      )
        return 0;
    }
    return 1;

대각선에 응시자가 있고, 대각선 위치로 상/하/좌/우 등으로 이동하는 2개의 경로에 파티션이 없다면 거리두기를 위반했다.

그리고 이 3가지의 조건에서 모두 통과했다면, 해당 위치에 있는 응시자는 거리두기를 위반하지 않았다.

 

현재 대기실에 위치한 모든 응시자가 이 3가지 검증 과정을 통과할 때 이 대기실은 거리두기를 위반하지 않았다고 할 수 있다.

 

  return places.map((place) => {
    for (let i = 0; i < w; i++) {
      for (let j = 0; j < h; j++) {
        if (place[i][j] === 'P') {
          if (!checkDistance(i, j, place)) return 0;
        }
      }
    }
    return 1;
  });

places에는 몇 개의 대기실들의 정보가 있으며, 각 인덱스에 해당하는 place에는 하나의 대기실에 있는 응시자 위치 정보가 있다.
하나의 대기실 안에서 한명이라도 거리두기를 위반했다면, 0을 반환하며 종료하고, 모두 거리두기를 지켰다면 1을 반환한다.

---

여기는 헤맸던 부분인데, 오류인지 아닌지 정확한 원인을 잘 모르겠다.

응시자 간의 거리두기를 확인하면서, 처음에는

 

place[x+dx1[i]][y+dy1[i]] === '0' 로 빈 테이블을 검증했었다.

 

이미 첫 번째 1 맨하탄 거리를 검증하면서, 상하좌우에 응시자가 존재한다면 거리두기가 실패이므로,
2,3번째의 거리 검증에서는 1 맨하탄 거리에 다른 응시자는 위치할 수가 없다고 생각했다.

 

그러므로 1 맨하탄 거리에는 빈 테이블(0) 와 파티션(X) 둘 중 하나만 올 수 있어서 빈 테이블인지를 검증했고,
3?4가지 정도의 테스트케이스가 실패했었다.

 

여러 시도를 하다가,

place[x+dx1[i]][y+dy1[i]] !== 'X' 로 파티션이 없을때를 검증하였더니, 테스트케이스가 통과하더라.

 

문제에서 쓰인 '0'문자 문제인지, 아니면 미처 고려하지 못한 부분이 있는건지..? 아직 어떤게 문제인지는 잘 모르겠다.