[알고리즘 연습] 프로그래머스 거리두기 확인하기 (LEVEL 2, 자바스크립트)

문제

프로그래머스

---

풀이

• 대기실의 갯수와 한 대기실의 행과 열의 최댓값이 5로 크지 않았기 때문에 for문을 중첩해서 풀어도 시간초과가 나지 않는다.
• 대기실 배열을 순회하면서 해당 지점에 사람(P)이 있을 때, 8방향을 모두 탐색하며 거리두기를 확인한다.
  • 상하좌우를 해당 지점부터 2칸을 확인하고 대각선 방향은 해당 지점부터 1칸을 확인한다.
• 대각선 방향의 경우 두 사람이 맨해튼 거리를 유지하고 있지 않다면 행 기준 더 위에 있는 사람의 아래에 파티션, 행 기준 더 아래에 있는 사람의 위에 파티션이 있는지 확인해야 한다. 이 때 두 곳 중 한 곳이라도 파티션이 없다면 거리두기를 지키지 않은 것이다.
• 복잡한 구현 문제였지만, 최대한 깔끔하게 풀어보기 위해 노력했다.

소스 코드

function solution(places) {
    const answer = [];
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
    
    for (const place of places) {
      let flag = false;
    
      for (let i = 0; i < 5; i++) {
        for (let j = 0; j < 5; j++) {
          if (place[i][j] !== 'P') continue;
          
          for (let k = 0; k < 4; k++) {
            for (let l = 1; l <= 2; l++) {
              const nx = i + (dirs[k][0] * l);
              const ny = j + (dirs[k][1] * l);
                
              if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) break;
              if (place[nx][ny] === 'X') break;
              if (place[nx][ny] === 'P') {
                flag = true;
                break;
              }  
            }
          }
          
          for (let k = 4; k < 8; k++) {
            const nx = i + dirs[k][0];
            const ny = j + dirs[k][1];
            
            if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
            if (place[nx][ny] === 'P') {
              if (nx > i && (place[nx - 1][ny] !== 'X' || place[i + 1][j] !== 'X')) {
                flag = true;
              }
              
              if (nx < i && (place[nx + 1][ny] !== 'X' || place[i - 1][j] !== 'X')) {
                flag = true;
              }
            }
          }
        }
      }
      
      if (!flag) answer.push(1);
      else answer.push(0);
    }
    
    return answer;
}