문제 설명 및 링크

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

나의 풀이

대학교때 문제해결 강의에서 풀었었던 최단 거리 구하기가 생각났다.

2차원 배열이 주어졌을때, 특정 좌표에서 특정 좌표로 이동할때 가장 최단 거리를 구하는 문제...

그때 당시에는 밤새서 고민해도 못풀었던 기억이 있는데... 지금은 그냥 푸는 거 보니 역시 쓸데없는 배움이란 건 없나 보다.

어쨌거나, 이 문제도 비슷한 문제라고 생각하고 풀었고 통과 완료.

핵심은 x, y 의 증감 + distance 의 증가와 함께 재귀를 돌리면서, 타겟 P 와의 거리가 2 이하인 또다른 P 를 찾으면 false, 또다른 P 가 없으면 true 리턴한다.

• 루프를 돌면서 P 를 찾아 재귀함수 실행
  • 이때 x, y 좌표와 함께 distance 를 0 으로 해서 호출
• 재귀함수 로직
  • 현재 distance 가 2 초과면 --> 거리두기 조건 clear 이므로 true 리턴
  • 현재 위치에 X 가 있으면 --> 막힌 곳 - 갈 수 없는 곳이므로 true 리턴
  • left, right, up, down 방향으로 재귀함수 호출
    • 방향에 따라 x, y 증감
    • distance 는 1 증가
    • 재귀함수가 false 를 리턴하면 거리두기 실패하는 사례가 있다는 얘기므로 false 리턴
  • 위 코드 다 통과하면 모든 경우가 true 란 소리이므로 true 리턴

코드

모든 프로그래머스 문제 관련 코드들은 GitHub 링크 에 있음.

const checkDistance = (arr, x, y, distance, direction) => {
    if (distance > 2 || arr[x][y] === 'X') {
        return true;
    }
    
    if (distance > 0 && arr[x][y] === 'P') {
        return false;
    }
    
    if (direction !== 'right' && x > 0) {
        if (!checkDistance(arr, x - 1, y, distance + 1, 'left')) {
            return false;
        }
    }
    if (direction !== 'left' && x < 4) {
        if (!checkDistance(arr, x + 1, y, distance + 1, 'right')) {
            return false;
        }
    }
    if (direction !== 'down' && y > 0) {
        if (!checkDistance(arr, x, y - 1, distance + 1, 'up')) {
            return false;
        }
    }
    if (direction !== 'up' && y < 4) {
        if (!checkDistance(arr, x, y + 1, distance + 1, 'down')) {
            return false;
        }
    }
    
    return true;
};

const isOk = arr => {
    for (let x = 0; x < arr.length; x++) {
        for (let y = 0; y < arr.length; y++) {
            if (arr[x][y] === 'P' && !checkDistance(arr, x, y, 0)) {
                return 0;
            }
        }
    }
    
    return 1;
};

function solution(places) {
    var answer = [];
    
    places.map(place => {
        answer.push(isOk(place.map(p => p.split(''))));
    });
    
    return answer;
}