[해커랭크] Queen's Attack II

[해커랭크] Queen's Attack II

 

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

Queen's Attack II | HackerRank

 

 

 

You will be given a square chess board with one queen and a number of obstacles placed on it. Determine how many squares the queen can attack.퀸 하나와 여러 장애물이 놓인 정사각형 체스판이 주어집니다. 여왕이 공격할 수 있는 칸의 수를 결정하세요.

A queen is standing on an  chessboard. The chess board's rows are numbered from  to , going from bottom to top. Its columns are numbered from  to , going from left to right. Each square is referenced by a tuple, , describing the row, , and column, , where the square is located.퀸이 체스판 위에 서 있습니다. 체스판의 행은 아래에서 위로 번호가 매겨져 있습니다. 열은 왼쪽에서 오른쪽으로 번호가 매겨져 있습니다. 각 정사각형은 해당 정사각형이 위치한 행, 열, 를 나타내는 튜플 로 참조됩니다.

The queen is standing at position . In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from :여왕이 위치에 서 있다. 한 번의 이동으로 그녀는 8방향(좌, 우, 위, 아래, 네 대각선 방향) 중 어느 칸이든 공격할 수 있습니다. 아래 도표에서 초록색 원은 여왕이 공격할 수 있는 모든 세포를 나타냅니다:

There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location  in the diagram above prevents the queen from attacking cells , , and :체스판에는 장애물이 있는데, 각 장애물은 여왕이 그 경로 밖의 칸을 공격할 수 없게 막습니다. 예를 들어, 위 다이어그램 위치에 장애물이 있으면 여왕이 세포 , , , 를 공격하지 못하게 한다:

Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at . In the board above, there are  such squares.여왕의 위치와 모든 장애물 위치를 고려하여, 여왕이 위치에서 공격할 수 있는 칸의 수를 찾아 출력합니다. 위 보드에는 그런 사각형들이 있습니다.

Function Description기능 설명

Complete the queensAttack function in the editor below.아래 편집기에서 queensAttack 기능을 완료하세요.

queensAttack has the following parameters:
- int n: the number of rows and columns in the board
- nt k: the number of obstacles on the board
- int r_q: the row number of the queen's position
- int c_q: the column number of the queen's position
- int obstacles[k][2]: each element is an array of  integers, the row and column of an obstaclequeensAttack은 다음과 같은 매개변수를 가집니다: - int n: 보드의 행과 열 수 - nt k: 보드 위의 장애물 수 - int r_q: 퀸 위치의 행 번호 - int c_q: 퀸 위치의 열 번호 - int 장애물[k][2]: 각 요소는 정수 배열입니다, 장애물의 행과 열입니다

Returns
- int: the number of squares the queen can attack리턴스 - 정수: 여왕이 공격할 수 있는 칸의 개수입니다

Input Format입력 형식

The first line contains two space-separated integers  and , the length of the board's sides and the number of obstacles.
The next line contains two space-separated integers  and , the queen's row and column position.
Each of the next  lines contains two space-separated integers  and , the row and column position of .첫 번째 줄은 두 개의 공간 분리 정수와 , 보드 변의 길이와 장애물 수를 포함합니다. 다음 줄은 두 개의 공간 구분 정수와 , 퀸의 행과 열의 위치를 포함한다. 다음 각 줄은 두 개의 공간 분리 정수와 , 즉 의 행과 열 위치를 포함한다.

Constraints제약 조건

•  
•  
• A single cell may contain more than one obstacle.하나의 셀에는 여러 개의 장애물이 포함될 수 있습니다.
• There will never be an obstacle at the position where the queen is located.여왕이 위치한 위치에는 결코 장애물이 존재하지 않습니다.

Subtasks하위

For  of the maximum score:최대 점수를 위한 것:

•  
•  

For  of the maximum score:최대 점수를 위한 것:

•  
•  

Sample Input 0샘플 입력 0

4 0
4 4

Sample Output 0샘플 출력 0

9

Explanation 0설명 0

The queen is standing at position  on a  chessboard with no obstacles:여왕은 장애물이 없는 체스판 위에 서 있습니다:

Sample Input 1샘플 입력 1

5 3
4 3
5 5
4 2
2 3

Sample Output 1샘플 출력 1

10

Explanation 1설명 1

The queen is standing at position  on a  chessboard with  obstacles:퀸은 장애물이 있는 체스판 위에 서 있습니다:

The number of squares she can attack from that position is .그 위치에서 공격할 수 있는 칸 수는 입니다.

Sample Input 2샘플 입력 2

1 0
1 1

Sample Output 2샘플 출력 2

0

Explanation 2설명 2

Since there is only one square, and the queen is on it, the queen can move 0 squares.칸이 하나뿐이고 퀸이 그 위에 있기 때문에 퀸은 0칸을 움직일 수 있습니다.

 

 

 

첫번째 풀이 (오답)

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'queensAttack' function below.

     *

     * The function is expected to return an INTEGER.

     * The function accepts following parameters:

     *  1. INTEGER n

     *  2. INTEGER k

     *  3. INTEGER r_q

     *  4. INTEGER c_q

     *  5. 2D_INTEGER_ARRAY obstacles

     */

    public static int queensAttack(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {

    // Write your code here

   

        if(n==1){

            return 0;

        }

   

       

        // n x n

        // init        

        int dap = 0;

        int[][] map = new int[n+1][n+1];

        // obsatcles setting

        for(List<Integer> ob : obstacles){

            int ob_y = ob.get(0);

            int ob_x = ob.get(1);

            map[ob_y][ob_x] = -1;

        }

        // search

        int cur_y = r_q;

        int cur_x = c_q;

        int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

        int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};

       

        for(int i=0; i<8; i++){

            int ny = cur_y + dy[i];

            int nx = cur_x + dx[i];

           

            while(1 <= ny && ny <= n && 1 <= nx && nx <= n){

                if( map[ny][nx] == -1 ){    // obstacle

                    break;

                }

                dap++;

                ny += dy[i];

                nx += dx[i];

            }

        }

       

       

        return dap;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int r_q = Integer.parseInt(secondMultipleInput[0]);

        int c_q = Integer.parseInt(secondMultipleInput[1]);

        List<List<Integer>> obstacles = new ArrayList<>();

        IntStream.range(0, k).forEach(i -> {

            try {

                obstacles.add(

                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

                        .map(Integer::parseInt)

                        .collect(toList())

                );

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

        });

        int result = Result.queensAttack(n, k, r_q, c_q, obstacles);

        bufferedWriter.write(String.valueOf(result));

        bufferedWriter.newLine();

        bufferedReader.close();

        bufferedWriter.close();

    }

}

 

 

 

2차원 배열(int[n][n]) 사용시, 최대 n이 10,000 인것을 고려하면,

10000 x 10000 = 100,000,000
int가 4바이트니까 400000000 (4억바이트)
메모리 400MB 필요하니 런타임 에러 발생

 

두번째 풀이 => 그리디 알고리즘으로 8가지 방향에 대해서, 최단거리 장애물 찾기

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'queensAttack' function below.

     *

     * The function is expected to return an INTEGER.

     * The function accepts following parameters:

     *  1. INTEGER n

     *  2. INTEGER k

     *  3. INTEGER r_q

     *  4. INTEGER c_q

     *  5. 2D_INTEGER_ARRAY obstacles

     */

    public static int queensAttack(int n, int k, int r_q, int c_q, List<List<Integer>> obstacles) {

    // Write your code here

   

        // n x n

        // obstacles[k][2]

       

        // init

        int dap = 0;

        int queen_y = r_q;

        int queen_x = c_q;

       

        // get distance (queen~edge)

        int up = n-queen_y;

        int down = queen_y-1;

        int right = n-queen_x;

        int left = queen_x-1;

       

        int up_right = Math.min(up, right);     // 43, 54, 65

        int down_right = Math.min(down, right); // 43 34 25

        int down_left = Math.min(down, left);   // 43 32 21

        int up_left = Math.min(up, left);       // 43 52 61

        // obsatcles search

        for(List<Integer> ob : obstacles){

            int ob_y = ob.get(0);

            int ob_x = ob.get(1);

           

            // up & down (same column)

            if(queen_x == ob_x){

                if(ob_y > queen_y){ up = Math.min(up, ob_y-queen_y-1); }  // up

                else{ down = Math.min(down, queen_y-ob_y-1); }    // down

            }

           

            // right & left (same row)

            else if(queen_y == ob_y){

                if(ob_x > queen_x){ right = Math.min(right, ob_x-queen_x-1); }

                else{ left = Math.min(left, queen_x-ob_x-1); }

            }

           

            // other

            else if(Math.abs(queen_y-ob_y) == Math.abs(queen_x-ob_x)){

                // up_right

                if(ob_y > queen_y && ob_x > queen_x){ up_right = Math.min(up_right, ob_y-queen_y-1); }

               

                // down_right

                else if(queen_y > ob_y && ob_x > queen_x){ down_right = Math.min(down_right, queen_y-ob_y-1); }

               

                // down_left

                else if(queen_y > ob_y && queen_x > ob_x){ down_left = Math.min(down_left, queen_y-ob_y-1); }

               

                // up_left

                else if(ob_y > queen_y && queen_x > ob_x){ up_left = Math.min(up_left, ob_y-queen_y-1); }

            }

           

        }

       

        dap = up + down + right + left + up_right + down_right + down_left + up_left;

        return dap;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int r_q = Integer.parseInt(secondMultipleInput[0]);

        int c_q = Integer.parseInt(secondMultipleInput[1]);

        List<List<Integer>> obstacles = new ArrayList<>();

        IntStream.range(0, k).forEach(i -> {

            try {

                obstacles.add(

                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

                        .map(Integer::parseInt)

                        .collect(toList())

                );

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

        });

        int result = Result.queensAttack(n, k, r_q, c_q, obstacles);

        bufferedWriter.write(String.valueOf(result));

        bufferedWriter.newLine();

        bufferedReader.close();

        bufferedWriter.close();

    }

}