[구현] 거리두기 확인하기 (2021 카카오 채용연계형 인턴십)

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

 

첫번째 풀이 (성공)

0,0이 P기준 맨해튼거리 2이하 범위

• P를 기준으로 맨해튼거리 2는 상하좌우 2칸씩, 대각선 1칸씩이다.
• 이 범위안에 P가 있다면
  • P와 P사이에 X가 있는지. (PXP)
  • P와 P가 대각선에 있을때 양옆에 X가 있는지를 확인해야한다 

 

맨해튼 거리 2이하의 범위를 3파트 로직으로 나누고

P를 찾았을떄 해당 위치 기준 위의 로직에 걸리는 경우가 있으면 0리턴 전부 통과하면 1을 리턴했다.

 

• 범위1. P기준 1칸 상하좌우 
  
  • P가 있으면 0을 리턴
• 범위2. P기준 1칸 대각선
  • P가 있는데 양옆 X가 없음 0을 리턴
• 범위3. P기준 2칸 상하좌우
  • P가 있는데 사이에 X가 없음 0 리턴

 

범위2 대각선 P의 양 옆 좌표구하기

예를들어 (a, b) 좌표의 양 옆을 구한다고 치자

P로부터 (a, b) 의 이동이 1이냐  -1이냐에 따라 다르다

P 기준 (1, -1) 이동했을 때 양옆은 (a-1, b) 와 (a, b+1) 이다

 

// 범위안
// P기준 상하좌우 1칸씩
const rangeA = [
    [0,1],
    [1,0],
    [0,-1],
    [-1,0],
]
// P기준 대각선 1칸씩
const rangeB = [
    [1,1],
    [1,-1],
    [-1, 1],
    [-1, -1],
]
// P기준 상하좌우 2칸씩
const rangeC = [
    [0,2],
    [2,0],
    [0, -2],
    [-2, 0]
]

function isInsideMap(r, c) {
    return r >= 0 && r < 5 && c >= 0 && c < 5;
}

// 거리두기 지키는지 확인하는 함수
function isValid(currRow, currCol, map) {
    // 가장 최측근
    for (const [moveR, moveC] of rangeA) {
        const nextR = currRow + moveR;
        const nextC = currCol + moveC;
        if(!isInsideMap(nextR, nextC)) continue; // 5x5를 벗어나면 패쓰
        // 가장 최측근인데 P가 있으면 탈락
        if (map[nextR][nextC] === 'P') return false;
    }
    // 대각선
    for (const [moveR, moveC] of rangeB) {
        const nextR = currRow + moveR;
        const nextC = currCol + moveC;
        if(!isInsideMap(nextR, nextC)) continue; // 5x5를 벗어나면 패쓰
        
        // 대각선에 P가 있음
        if (map[nextR][nextC] === 'P') {
            const first = moveR > 0 ? -1 : 1;
            const second = moveC > 0 ? -1 : 1; 
            // 양옆에 X가 없음 탈락
            if (!(map[nextR + first][nextC] === 'X' && map[nextR][nextC+second])) {
                return false;
            }
        }
    }
    
    // 가장 끝
     for (const [moveR, moveC] of rangeC) {
        const nextR = currRow + moveR;
        const nextC = currCol + moveC;
        if(!isInsideMap(nextR, nextC)) continue; // 5x5를 벗어나면 패쓰
        const midR = (currRow + nextR)/2;
        const midC = (currCol + nextC)/2;
        // 끝이 P인데 끝과 중심 사이에 X가 없음 탈락
        if (map[nextR][nextC] === 'P' && map[midR][midC] !== 'X') return false;
    }
    return true;
}

function solution(places) {
    var answer = [];
    for (let i = 0; i < 5; i++) {
        const currPlace = places[i]; // 5x5
        const map = []; 
        currPlace.forEach(row => map.push(row.split(''))); // 5x5 arr형태로 변환
        let isWrong = false;
        
        for (let r = 0; r < 5; r++) {
            for (let c = 0; c < 5; c++) {
                // P기준 거리두기를 안 지켰다
                if (map[r][c] === 'P' && !isValid(r, c, map)) {
                    isWrong = true;
                    break;
                }
            }
            if(isWrong) break;
        }
        answer.push(isWrong ? 0 : 1)
    }
    return answer;
}

\

 

 

두번째 풀이 DFS

P기준으로 거리가 2이내에 다른 사람이 있나 확인 BFS