[HackerRank] Queen's Attack II

https://www.hackerrank.com/challenges/queens-attack-2/problem?isFullScreen=true

Queen's Attack II | HackerRank

 

answer = 24

퀸이 이동할 수 있는 칸의 개수를 구하는 문제이다.

이런 문제가 나왔을 때 내가 기존에 풀던 방식으로 우선 풀어보았다.

결론부터 말하자면 아래는 실패한 코드이다.

int DFS(int count, int n, const vector<vector<char>>& board, int r, int c, vector<int> dir)
{
    int nextR = r + dir[0];
    int nextC = c + dir[1];

    if ( !(nextR >= 0 && nextC >= 0 && nextR < n && nextC < n) || board[nextR][nextC] == 0)
        return count;

    return DFS(count + 1, n, board, nextR, nextC, dir);
}

int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {
    vector<vector<char>> board(n, vector<char>(n, 1));

    for (auto obstacle : obstacles)
        board[obstacle[0] - 1][obstacle[1] - 1] = 0;

    int answer = 0;
    answer += DFS(0, n, board, r_q-1, c_q-1, { -1, 0});
    answer += DFS(0, n, board, r_q-1, c_q-1, { 0,-1 });
    answer += DFS(0, n, board, r_q-1, c_q-1, { 1, 0 });
    answer += DFS(0, n, board, r_q-1, c_q-1, { 0, 1 });
    answer += DFS(0, n, board, r_q-1, c_q-1, { -1,-1 });
    answer += DFS(0, n, board, r_q-1, c_q-1, { 1, 1 });
    answer += DFS(0, n, board, r_q-1, c_q-1, { -1,1 });
    answer += DFS(0, n, board, r_q-1, c_q-1, { 1,-1 });

    return answer;
}

 

왜 실패했을까? 틀린 이유는 아래와 같다. 우선 조건을 살펴보자.

0 < n ≤ 1000 , 0 ≤ k ≤ 10^5 이다.

보드판의 2중벡터를 두려면 1000 * 1000 짜리 벡터(나 배열)이 만들어진다. 그리고 장애물의 개수는 10^5 가 맥시멈이다. 따라서 n*n 만큼의 배열은 절대 가질 수 없으며 (메모리초과) 앞과 같은 이유로 여왕이 움직일 수 있는 칸도 일일이 확인할 수 없다.

장애물의 개수만큼만 for문을 도는것이 제한이 되는 문제이다.

 

사실 단순 연산으로 이 문제는 해결가능하다.

퀸의 위치가 주어졌으므로 장애물을 제외하고 퀸이 상하좌우로 움직일 수 있는 칸의 개수를 구할 수 있다.

마찬가지로 장애물을 제외하고 움직일 수 있는 대각선의 개수도 쉽게 구할 수 있다. 아래는 대각선의 개수를 쉽게 구하는 방법이다.

왼쪽위로 뻗어나가는 대각선은 왼쪽 & 위쪽 으로 이동할 수 있는 칸중에서 작은 값이다.

똑같이 2번째 사진을 보면 왼쪽으로 이동할 수 있는 칸 = 2, 위쪽으로 이동할 수 있는 칸 = 3 이므로 왼쪽위로 이동가능한 칸의 개수는 min(2,3) 이 되어 2가 된다.

먼저 이렇게 8방향의 값들을 전부 구한다.

장애물들에 대한 계산 또한 간단하다. 상하좌우에 있는 장애물들은 현재 퀸의 위치에서 x나 y 좌표의 값이 같아진다. 대각선에 있는 장애물은 장애물의 위치에서 퀸의 위치를 뺐을 때 x,y 의 값이 같아진다. 대각선을 이루는 장애물은 장애물부터 퀸까지 사각형을 만들었을 때 무조건 정사각형이 된다는 뜻이다.

이렇게 하면 현재 장애물이 대각선의 위치에 있는지를 알 수 있고 1,2,3,4 분면 중 어떤 분면에 있는지 확인하여 바꿔야하는 변수를 확인해준다. 그 뒤에 장애물부터 퀸까지의 거리는 넓이와 높이가 동일하므로 (무조건 정사각형이므로) 넓이나 높이에서 -1 을 해주면 된다.

int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles) {
    int top = r_q - 1;
    int bottom = n - r_q;
    int left = c_q - 1;
    int right = n - c_q;

    int topleft = min(top, left);
    int topright = min(top, right);
    int bottomleft = min(bottom, left);
    int bottomright = min(bottom, right);
    
    for (auto obstacle : obstacles)
    {
        // 상하좌우 최소값 갱신
        if (r_q == obstacle[0])
            obstacle[1] > c_q ? right = min(right, (obstacle[1] - c_q - 1)) : left = min(left, (c_q - obstacle[1] -1));
        if (c_q == obstacle[1])
            obstacle[0] > r_q ? bottom = min(bottom, (obstacle[0] - r_q - 1)) : top = min(top, (r_q - obstacle[0] - 1));

        // 대각선 갱신
        if (abs(obstacle[0] - r_q) == abs(obstacle[1] - c_q))
        {
            // 만족하면 대각선 위치에 있는 것.
            if (obstacle[0] < r_q && obstacle[1] < c_q)
                topleft = min(topleft, abs(obstacle[0] - r_q) - 1);
            else if (obstacle[0] < r_q && obstacle[1] > c_q)
                topright = min(topright, abs(obstacle[0] - r_q) - 1);
            else if (obstacle[0] > r_q && obstacle[1] < c_q)
                bottomleft = min(bottomleft, abs(obstacle[0] - r_q) - 1);
            else 
                bottomright = min(bottomright, abs(obstacle[0] - r_q) - 1);
        }
    }

    return top + bottom + left + right + topleft + topright + bottomleft + bottomright;
}

 

요즘은 코딩테스트 준비를 하면서 포스팅하지 않고 코딩테스트 문제만 풀고있는데 이 문제는 새로운 시각을 열어주는 문제인것 같아서 포스팅한다.