[HackerRank] Queen's Attack II

출처: https://www.hackerrank.com/challenges/queens-attack-2/problem

 Input 

5 3

4 3

5 5

4 2

2 3

　 

 Output 

10　

체스의 여왕(Queen)이 움질 수 있는 칸 수를 출력하는 문제이다.

위에서 처럼 임의의 위치에 장애물이 설치되어 있으면 해당 방향에 방해물 다음 지점으로는 움직일 수 없다.

 

문제 Test Case 중 두가지 조건이 있기에 주먹구구 방식으로는 통과할 수 없다.

  0 < n ≤ 1000

  0 ≤ k ≤ 10^5

- n*n 크기 만큼의 배열 가질 수 없다. → 메모리 초과

- 여왕이 움직일 수 있는 칸을 일일이 확인할 수 없다. → timeout 발생

→ 주먹구구식으로 하나하나 비교하지 않고, (key, value) 형식으로 구현

---

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        // 2차원 배열 동적 생성
        int n = sc.nextInt();
        int k = sc.nextInt();
         
        // 여왕 생성
        Vertex queen = new Vertex(sc.nextInt(), sc.nextInt());
         
        // 장애물 입력
        Map<String, String> obstacles= new HashMap<>();
        for(int i=0; i<k; i++) {
            // x,y 값을 하나의 key로 처리
            obstacles.put(sc.next() + "-" + sc.next(), "obstacle");
        }
     
        int answer = 0;
         
        // 여왕의 이동 범위를 입력(상하좌우 + 대각선)
        int[] x = {1,-1,0,0,-1,-1,1,1};
        int[] y = {0,0,1,-1,-1,1,-1,1};
         
        for(int i=0; i<x.length; i++) {
            // 초기 여왕의 위치를 입력
            int qx = queen.x;
            int qy = queen.y;
             
            // 이동 계산
            while(true) {
                // 여왕 이동
                qx = qx + x[i];
                qy = qy + y[i];
                 
                // 체스판을 초과하지 않는 범위 내에서
                if(qx <= 0 || qy <= 0 || qx > n || qy > n) {
                    break;
                }
                 
                String key = qx + "-" + qy;
                // 장애물을 만난 경우 stop (해당 key 장애물이 있는지 확인)  
                if(obstacles.containsKey(key)) {
                    break;
                }
                answer++;
            }
        }
        System.out.println(answer);
    }
 
}
class Vertex{
    int x, y;
     
    public Vertex(int x, int y) {
        this.x = x;
        this.y = y;
    }
}