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

📙 1. 문제

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

문제 설명

풀이 1 : 내 풀이

풀이 과정

1. 맨해튼 거리를 이동 거리에 따라 A, B, C로 구분

2. A : 네 방향으로 2칸 이동 -> 사이에 X가 1개 있다면 지킴

3. B : 대각선으로 이동 -> 사이에 X가 2개 있다면 지킴

3. C : 네 방향으로 1칸 이동 -> 무조건 지키지 않음

function solution(places) {
    const result = []
    const manhatenA = [[2,0],[-2,0],[0,2],[0,-2]]
    const manhatenB = [[1,1],[1,-1],[-1,1],[-1,-1]]
    const manhatenC = [[1,0],[-1,0],[0,1],[0,-1]]
    
    const isGood = (arr,y,x) => {
        for(let i=0;i<4;i++){ // P가 위치에 있다면 무조건 false
            let item = manhatenC[i];
            const [goY,goX] = [y+item[0],x+item[1]];
            if(goY>=5 || goX>=5 || goY<0 || goX<0) continue;
            
            if(arr[goY][goX]==='P') return false;
        }
        for(let i=0;i<4;i++){ // 사이에 O가 있다면 무조건 false. P라면 manhatenC에서 이미 걸러짐
            let item = manhatenA[i];
            const [goY,goX] = [y+item[0],x+item[1]];
            if(goY>=5 || goX>=5 || goY<0 || goX<0) continue;
            
            const [middleY,middleX] = [y+item[0]/2,x+item[1]/2]
            
            if(arr[goY][goX]==='P' && arr[middleY][middleX]==='O') return false;
        }
        for(let i=0;i<4;i++){ // 칸막이가 둘 사이에 2개 있어야 함
            let item = manhatenB[i];
            const [goY,goX] = [y+item[0],x+item[1]];
            if(goY>=5 || goX>=5 || goY<0 || goX<0) continue;
            
            if(arr[goY][goX]==='P'){
                let [middleY,middleX] = [y,x+item[1]]
                if(arr[middleY][middleX]==='O') return false;

                [middleY,middleX] = [y+item[0],x]
                if(arr[middleY][middleX]==='O') return false;
            }
        }
        return true;   
        
    }
    
    places.forEach((place)=>{
        let isGoodBoolean = true;
        place.forEach((column,y)=>{
            column.split('').forEach((person,x)=>{
                if(person==='P') {
                    if(!isGood(place,y,x)) isGoodBoolean=false;
                }
            })
        })
        result.push(isGoodBoolean?1:0)
    })    
    return result;
}

 

 풀이 2 : 다른 사람 풀이

링크

풀이 과정

1. for문을 돌려 places의 각 요소를 iskeepingDistance함수에 넣었다.

2. split('')을 통해 string -> 배열로 변환시켜 준다.

3. 방을 탐색하다가 'P'를 만나면 queue에 push 한다.

4. for문을 이용하여 상하좌우를 탐색하여 X라면 continue, P라면 0을 return 한다.

5. 각 경우 별로 for문을 이용하여 상하좌우를 한 번 더 더해준다. -> 2칸 맨해튼 거리까지 탐색

const iskeepingDistance = (place) => {
  let roomInfo = place.map((rooms) => rooms.split(''));

  let queue = [];
  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      if (roomInfo[i][j] === 'P') {
        queue.push([i, j]);
      }
    }
  }

  let dx = [-1, 1, 0, 0];
  let dy = [0, 0, 1, -1];

  while (queue.length) {
    const [x, y] = queue.shift();

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];

      if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
      if (roomInfo[nx][ny] === 'X') continue;
      if (roomInfo[nx][ny] === 'P') return 0;

      for (let j = 0; j < 4; j++) {
        let aroundNX = nx + dx[j];
        let aroundNY = ny + dy[j];

        if (aroundNX < 0 || aroundNX >= 5 || aroundNY < 0 || aroundNY >= 5) continue;
        if (aroundNX === x && aroundNY === y) continue;
        if (roomInfo[aroundNX][aroundNY] === 'P') return 0;
      }
    }
  }

  return 1;
};

function solution(places) {
  let keepingDistance = [];
  for (let i = 0; i < 5; i++) {
    keepingDistance.push(iskeepingDistance(places[i]));
  }

  return keepingDistance;
}

내 풀이 보다 좀 더 복잡도는 늘었지만, 문제의 의도를 그래도 넣은 느낌이 있다. 한 칸 이동 후, 그 칸에서 한 칸을 더 이동하여 맨해튼 거리를 충족시킨다. 한 칸 이동하여 체크하고, 한 칸 이동하여 체크하여 내 풀이보다 깔끔한 풀이인 것 같다. 

 

---

🤔 2. 느낀 점

각각의 경우를 세분화하여 효과적으로 해결하였다. '모든 경우의 수를 탐색해야 한다'는 생각이 들자마자, DFS와 BFS라는 알고리즘을 고려했다. 실제로 DFS나 BFS를 사용하지는 않았지만, 모든 경우의 수를 탐색하면서 조건에 맞지 않는 경우에는 즉시 return false;를 사용하여 해당 탐색을 종료하는 방식으로 구현했다.
초반에 시간이 좀 걸리더라도 알고리즘을 제대로 생각하고, 설계한 후에 문제를 해결하는 방법을 적용하였다. 이렇게 풀이 하니 매우 효율적으로 문제에 접근할 수 있었다.

 

🤩 3. 한 번 더 짚고 갈 점

1. 1. forEach -> for문으로 변경할 때 체크할 점(forEach문과 for문의 차이점)
   1. return -> continue로 변경
   2. ({ }) -> (){}로 변경
   3. item = arr[i]추가 (forEach에서는 iterator를 알아서 돌지만, for문은 iterator에 직접 넣어야 함)