프로그래머스 | Level 2. 거리두기 확인하기

✅ 문제 링크

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

 

 

✏️ 조건

1. 두 사람의 맨해튼 거리가 2 초과여야 거리두기를 지킨 것이다.
   • 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 
2. 두 사람 사이에 파티션이 있다면, 지나갈 수 없으므로 거리두기를 지킨 것이다.
3. 대기실은 5개이고, 각 대기실의 크기는 5x5

 

✏️ My Solution - DFS

 

📌 접근법 

• DFS로 접근
• 사람의 위치 정보를 DFS에 보내서 해당 위치에서 거리 2 안에 사람이 있는지 확인.
• 두 사람의 거리가 맨해튼 거리가 아니라면, 무조건 0을 반환해야함.
• 파티션이 있는 경우엔 DFS로 탐색하지 않는다.

 

📌 solution code

function isPosible(p) {
    let dx = [1, -1, 0, 0];
    let dy = [0, 0, 1, -1];
    let flag = false;

    // L = 1 부터
    function DFS(L, x, y, curx, cury) {
      if (flag) return false;
      if (L > 2) {
        // 거리 2 이상이면 그만 찾아봐도 됨
        return true;
      } else {
        for (let i = 0; i < 4; i++) {
          let nx = curx + dx[i];
          let ny = cury + dy[i];
          if (
            nx >= 0 &&
            nx < 5 &&
            ny >= 0 &&
            ny < 5 &&
            (x !== nx || y !== ny)
          ) {
            if (p[nx][ny] === "O") {
              // 빈자리 였을 경우
              DFS(L + 1, x, y, nx, ny);
            } else if (p[nx][ny] === "P") {
              // 거리가 2이내인데 사람이였을 경우 => 거리두기 안지킴
              flag = true;
              return false;
            }
          }
        }
      }
    }

    // DFS 호출
    for (let i = 0; i < 5; i++) {
      for (let j = 0; j < 5; j++) {
        if (p[i][j] === "P") {
          // 거리두기 안지킨 경우를 찾아서, 한번이라도 안지켰으면 0반환
          flag = false;
          DFS(1, i, j, i, j);
          if (flag) {
            return 0;
          }
        }
      }
    }
    return 1;
  }
  function solution(places) {
    var answer = [];
    let n = places.length;

    for (let i = 0; i < n; i++) {
      answer.push(isPosible(places[i]));
    }
    return answer;
  }

 

 

❌ 꼬였던 부분

DFS의 최대 깊이로 탐색한 후, true를 반환하더라도, DFS의 최종 반환값이 true가 되지 않는다!!

따라서, 최대 깊이 까지 사람을 만나지 않고 무사히 탐색했더라도, 반환하는 값이 없다면... isPossible함수는 엉뚱하게 undefined를 반환하게 된다....

그래서 고민한 결과, DFS의 바깥에 flag를 세웠다. 탈출해야 하는 조건이 되면, flag를 true로 만들고, DFS를 그만 돌게 만들었다.

또한 DFS의 결과를 flag로 판단하니 문제가 잘 마무리 되었다.

 

❓궁금한 부분

보통 DFS의 경우에 check 배열 (또는 visit 배열)을 사용하여 탐색하는데, 그 방법을 사용하는 풀이를 시도하다가 실패하였다.

check배열을 사용하여 해결할 수 있는 방법은 없었을까?!