알고리즘 문제 풀이(프로그래머스 - 거리두기 확인하기)

프로그래머스 LEVEL 2(거리두기 확인하기)

• 사용 언어 : javascript

• 해결 날짜 : 2022-12-14

• 해결 방법 :

  • 각 places에 대한 응시자가 앉아있는 자리를 저장
  • check()를 통해 응시자끼리의 거리두기를 확인
    • 응시자끼리의 거리가 1인 경우, 0 반환
    • 응시자끼리의 거리가 2인 경우,
      • x좌표가 같은 경우(좌, 우)
      • y좌표가 같은 경우(앞, 뒤)
      • 대각선인 경우로 나눠서 문제 해결

• 회고 :

  • dfs로도 문제를 해결할 수 있을 것 같아 다음에 풀어보기

• 코드

  function solution(places) {
    const answer = [];
    const SIZE = 5;
  
    const check = (p, c) => {
      if (c.length <= 1) return 1;
  
      for (let i = 0; i < c.length - 1; i++) {
        for (let j = i + 1; j < c.length; j++) {
          const c1 = c[i],
            c2 = c[j];
          const dist = Math.abs(c2[0] - c1[0]) + Math.abs(c2[1] - c1[1]);
  
          if (dist === 1) return 0;
          else if (dist === 2) {
            if (c1[0] === c2[0]) {
              if (p[c1[0]][c1[1] + 1] !== 'X') return 0;
            } else if (c1[1] === c2[1]) {
              if (p[c1[0] + 1][c1[1]] !== 'X') return 0;
            } else {
              const x = c1[0] - c2[0],
                y = c1[1] - c2[1];
  
              if (p[c2[0] + x][c2[1]] !== 'X' || p[c2[0]][c2[1] + y] !== 'X') return 0;
            }
          }
        }
      }
      return 1;
    };
  
    for (const place of places) {
      const p = place.map((p) => p.split(''));
      const candidates = [];
  
      for (let x = 0; x < SIZE; x++) {
        for (let y = 0; y < SIZE; y++) {
          if (p[x][y] === 'P') {
            candidates.push([x, y]);
          }
        }
      }
  
      answer.push(check(p, candidates));
    }
  
    return answer;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges