[JS] 거리두기 확인하기

예에에전에 아무것도 모르는 상태에서 코딩테스트란 얼마나 어려울까...?

이런 생각으로 카카오 인턴 코테를 본적이 있는데요.

그때 이 문제를 처음보고 2시간 동안 고민하다가 결국에 1sol로 끝나고 "난 안맞나보다... 하하" 이런 기억이 나네요.

 

프로그래머스 level 2 문제였고 생각보다 쉽게 풀렸습니다.

다들 어떻게 푸셨나요? 같이 한번 살펴볼까요?

 

---

문제 요약

• 입출력 예

places	result
[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]	[1, 0, 1, 1, 1]

• 간단한 문제 요약

1) P는 지원자의 위치, O는 비어있는 공간, X는 칸막이로 막혀있는 공간입니다.

2) 문제에서는 맨해튼 거리(|x2- x1| + |y2 - y1|)이 2 이하이면서 칸막이가 없다면 거리두기 위반입니다.

3) 맨해튼 거리가 2이하여도 칸막이(X)가 있다면 거리두기를 만족하고 있습니다.

 

 

문제 해석

먼저 정말 오랜만에 dfs 문제 중에서도 단위 거리만큼 이동하는 문제를 풀게 되었습니다.

 방문한 위치를 기록해두면서 방문한 곳은 다시 안가도록하여 무한 루프에 빠지는 것을 방지했습니다.

 

또 칸막이(X)를 어떻게 처리해야할까하는 과제가 있는데요.

기준 위치에 대해 상하좌우로 이동에 대한 반복문 안에서 칸막이가 나온다면 그 분기는 아무것도 안해주는 걸로 처리했습니다.

 

전체 코드를 먼저 확인해보고 주요한 로직 코드를 리뷰해보죠.

 

정답 코드

function check(x, y, visited) {
    //이 좌표가 5x5를 벗어나진 않았는지, 방문한 곳을 다시 간 것은 아닌지 확인
    if (x < 0 || x > 4 || y < 0 || y > 4) {
        return false;
    } else if (!visited.includes(`${x}${y}`)) return true;
    return false;
}

function move(place, position, visited, level) {
    if (level > 1) return true;
    const dx = [0, -1, 0, 1];
    const dy = [-1, 0, 1, 0];
    
    const newvisited = [...visited, position.join("")];
    const result = [];
    
    for (let i = 0; i < 4; i++) {
        const row = position[0] + dx[i];
        const col = position[1] + dy[i];
        
        if (check(row, col, visited)) {
            if (place[row][col] === "P") {
                return false;
            }
            else if (place[row][col] === "O") {
                result.push(bfs(place, [row, col], newvisited, level + 1));
            } else continue;
        }
    }
    return !result.includes(false);
}

function solution(places) {
    const result = Array(places.length).fill(0);
    places.forEach((place, index) => {
        const positions = [];
        for (let i = 0; i < 5; i++) {
            for (let j = 0; j < 5; j++) {
                if (place[i][j] === "P") positions.push([i, j]);
            }
        }
        let isOkay = true;
        for (const position of positions) {
            if (!move(place, position, [], 0)) {
                isOkay = false;
                break;
            }
        }
        if (isOkay) result[index] = 1;
    });
    return result;
}

 

• 어떻게 흘러가는지
  1. solution - 1
     
     1. 일단 지원자 위치를 다 찾아서 positions 배열에 넣어줍니다.
     2. 각 위치 별로 거리두기를 만족하는지 move 함수로 확인해줍니다.
  2. move - 1
     1. 현재 좌표를 visited 스택에 string으로 넣어줍니다.(전 그냥 편의상 이렇게 했어요.)
     2. 거리 유닛 dx, dy에 대한 loop를 돌면서 check 함수로 확인한다.
  3. check
     1. 5x5 그래프의 index를 넘지는 않는지, 이미 방문한 적있는 좌표인지 확인해서 boolean 값을 return.
  4. move - 2
     1. 지원자가 있는 경우(P): 무조건 맨해튼 거리안에서만 move가 실행되므로 false를 return.
     2. 빈공간인 경우(O): 재귀 실행.
     3. 칸막이인 경우(X): 아무것도 하지 않는다. continue;
  5. solution - 2
     1. loop의 결과를 출력합니다.

 

하나하나 보면 별거 아닌데 너무 장황한 설명이 아이디어를 못떠올리게 하네요.

칸막이를 만났을 때 아무것도 하지 않아야한다는게 가장 중요한 부분이 아닌가 싶습니다.

 

그럼 이만!