[Algorithm] queens-attack-2 풀이

안녕하세요 개발자 Sean입니다. 

 

오늘은 queens attack이라는 문제를 풀어보았습니다.

해답 코드는 아래와 같습니다. 

 

function queensAttack(n, k, r_q, c_q, obstacles) {
    // Write your code here
    let left = 1;
    let right = n;
    let high = n;
    let bottom = 1;
   
    const equation = (x) => x + (r_q - c_q);
    const revEquation = (x) => -x + (r_q + c_q);
    const getX = (y) => y - (r_q - c_q); 
    const getrevX = (y) => - y + (r_q + c_q); 
    
    let hightLeft = revEquation(1) > n ? getrevX(n) : 1;
    let hightRight = equation(n) > n ? getX(n) : n;
    let bottomLeft = equation(1) < 0 ? getX(1) : 1;
    let bottomRight = revEquation(n) < 0 ? getrevX(1) : n;
    
    const isOnLine = (x, y) => {
        const result = equation(x);
        if (result === y) return true;
        return false;
    }
    
    const isOnReverseLine = (x, y) => {
        const result = revEquation(x);
        if (result === y) return true;
        return false; 
    }
    
    for (let i = 0; i < obstacles.length; i ++) {
        const [row, col] = obstacles[i];
        if (row === r_q) {
            if (col < c_q && col > left) left = col + 1;
            if (col > c_q && col < right) right = col - 1;
            continue;
        }
        
        if (col === c_q) {
            if (row < r_q && row > bottom) bottom = row + 1;
            if (row > r_q && row < high) high = row - 1;
            continue;
        }
        
        if (isOnLine(col, row)) {
            if (col < c_q && col > bottomLeft) bottomLeft = col + 1;
            if (col > c_q && col < hightRight) hightRight = col - 1;
            continue;
        }
        
        if (isOnReverseLine(col, row)) {
            if (row < r_q && row > hightLeft) hightLeft = row + 1;
            if (row > r_q && row < bottomRight) bottomRight = row - 1;
            continue;
        }
    }
    
    const attackpointsOnX = right - left;
    const attackpointsOnY = high - bottom;
    const attackpointsOnL = 
        Math.sqrt(
            (hightRight - bottomLeft +1) * 
            (equation(hightRight) - equation(bottomLeft) +1)) -1;
    const attackpoinstOnRL = 
        Math.sqrt(
            (bottomRight - hightLeft +1) * 
            (revEquation(hightLeft) - revEquation(bottomRight) +1)) -1; 
        
    return attackpoinstOnRL + attackpointsOnL + attackpointsOnX + attackpointsOnY;
}

코드가 많이 복잡하네요. 아마 더 쉽게 해결하는 방법이 있을 텐데 제 실력으로는 이 정도가 아직까지는 한계인 듯합니다 ㅠㅠ 열심히 해야겠네요.

 

제가 생각한 풀이방법은 아래와 같습니다. 

 

퀸의 공격가능 루트는 네 가지입니다. 

• 수평
• 수직
• 기울기 1의 직선
• 기울기 -1의 직선

만약에 장애물이 위 루트에 놓여져 있다면 공격 가능한 위치의 개수는 그만큼 줄어들게 되겠죠. 

따라서 이러한 로직을 세워보았습니다. 

 

수평의 경우 left 초기값을 1로 두고 right 초기값을 n으로 설정합니다. 만약에 아무런 장애물이 없다면 수평선에서 공격 가능한 위치의 개수는 right - lieft +1이 될 겁니다.  

 

수직도 마찬가지 논리로 high는 n 그리고 bottom은 1로 값을 설정합니다. 

 

다음으로 기울기 1과 -1의 직선은 조금 까다로운 연산이 필요합니다. 

let hightLeft = revEquation(1) > n ? getrevX(n) : 1;
let hightRight = equation(n) > n ? getX(n) : n;
let bottomLeft = equation(1) < 0 ? getX(1) : 1;
let bottomRight = revEquation(n) < 0 ? getrevX(1) : n;

위와 같이 초기값을 설정했는데요,

eqation은 기울기가 1, revEquation은 기울기가 -1인 직선에서 x값을 넣으면 해당하는 y값을 반환하는 함수입니다. 

 

그래서 만약에 체스판을 넘어가는 값이 나오면 n 혹은 1로 값을 조정해주는 것입니다. 

 

이후로는 쉽습니다. 

 

장애물 리스트를 순환하면서, 

만약 해당 장애물이 

• 수평
• 수직
• 기울기 1의 직선
• 기울기 -1의 직선

위에 존재한다면 그에 맞게 left, right, high, bottom, hightLeft, hightRight, bottomLeft, bottomRight 값을 줄여나가는 것입니다. 

for (let i = 0; i < obstacles.length; i ++) {
        const [row, col] = obstacles[i];
        if (row === r_q) {
            if (col < c_q && col > left) left = col + 1;
            if (col > c_q && col < right) right = col - 1;
            continue;
        }
        
        if (col === c_q) {
            if (row < r_q && row > bottom) bottom = row + 1;
            if (row > r_q && row < high) high = row - 1;
            continue;
        }
        
        if (isOnLine(col, row)) {
            if (col < c_q && col > bottomLeft) bottomLeft = col + 1;
            if (col > c_q && col < hightRight) hightRight = col - 1;
            continue;
        }
        
        if (isOnReverseLine(col, row)) {
            if (row < r_q && row > hightLeft) hightLeft = row + 1;
            if (row > r_q && row < bottomRight) bottomRight = row - 1;
            continue;
        }
    }

그러면 아래와 같이 단순 빼기로 공격가능한 위치의 개수를 구할 수 있게 되는 것입니다. 

const attackpointsOnX = right - left;
    const attackpointsOnY = high - bottom;
    const attackpointsOnL = 
        Math.sqrt(
            (hightRight - bottomLeft +1) * 
            (equation(hightRight) - equation(bottomLeft) +1)) -1;
    const attackpoinstOnRL = 
        Math.sqrt(
            (bottomRight - hightLeft +1) * 
            (revEquation(hightLeft) - revEquation(bottomRight) +1)) -1;

혹시나 더 나은 방법이 있다면 공유 부탁드립니다.