[JS] DFS : 거리 두기 확인하기(2021 카카오 인턴십)

개요

상반기 카카오 인턴십 문제로 출제되었던 Level 2 코딩테스트 문제입니다. DFS를 충분히 활용해서 풀어야겠지만... 아직 이론을 이해하지 못해서ㅠ 코드가 길어진 것 같습니다.

문제

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

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

코드

🤩 : DFS로 풀기

function solution(places) {
  let answer = Array(places.length).fill(0);
  // 문자열로 주어지는 대기실을 배열로 변경하기
  places = places.map(p => p.map(i => i.split('')));

  // 상하좌우 좌표를 미리 선언해두기
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];

  for (let i = 0; i < places.length; i++) {
    DFS(i);
  }

  function DFS(lc) {
    answer[lc] = 1;
    let place = places[lc];
    // 행
    for (let i = 0; i < 5; i++) {
      // 열
      for (let j = 0; j < 5; j++) {
      
        // X, O인 경우는 탐색할 필요가 없으니 패스하기
        if (place[i][j] !== 'P') continue;
        
        for (let k = 0; k < 4; k++) {
          let nx = i + dx[k];
          let ny = j + dy[k];
          if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
            // 인접 상하좌우 좌표에 사람이 있다면 거리두기 미준수
            if (place[nx][ny] === 'P') {
              answer[lc] = 0;
              return;
            } else if (place[nx][ny] === 'O') {
              // 테이블이 있다면 다시 상하좌우 좌표를 확인하기
              for (let k2 = 0; k2 < 4; k2++) {
                let nx2 = nx + dx[k2];
                let ny2 = ny + dy[k2];
                
                // 현재 루프를 도는 좌표와 동일하면 미체크
                if(nx2 === i && ny2 === j) continue;
                if (nx2 >= 0 && nx2 < 5 && ny2 >= 0 && ny2 < 5) {
                
                  // 인접 상하좌우가 P O P인 상황으로 거리두기 미준수
                  if (place[nx2][ny2] === 'P') {
                    answer[lc] = 0;
                    return;
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  return answer;
}