[HackerRank] Queen's Attack II(Java)

## 접근방법

---

쉬워보였지만, 의외로 시간이 걸렸던 문제이다. 두 가지 접근 방법을 소개하려고 한다. 

 

 

첫번째로는 직관적으로 문제를 풀어보자. 퀸에서 출발하여, 벽을 만나는 순간의 여러 방향의 끝지점의 좌표를 미리 구해주자. 이제는 방해물 좌표를 가지고, 여러 방향의 끝지점 좌표들을 막을 수 있는지 확인해야 한다.

 

 

즉, 퀸, 장애물, 끝지점 좌표가 한 직선위에 있어야 한다. 수직선은 열이 모두 같아야 하고, 수평선은 행이 모두 같아야 한다. 대각선 일 때는, 기울기가 동일해야 한다.

 

 

위의 조건만으로는 부족하므로, 점의 대소 관계를 통해서 가운데 있음을 확인하면 된다.

 

 

첫번째 접근 방식은 구현이 지저분하다는 생각이 들었다. 구글링을 통해서 두번째 접근 방법을 알았다.

 

 

두번째 접근은 좀 더 직관적이다. 수직선, 수평선, 대각선의 끝지점을 0과 n + 1인 끝지점 변수들로 표현한다. 1과 n으로 표현하는것보다 계산이 편하다. 코드를 작성하다 보면 느낄 것이다.

 

 

장애물을 확인하면서, 수직선, 수평선, 대각선에 일치하는지 확인한다.

 

 

일치한다면, 값 갱신을 통해서 끝지점 변수들을 업데이트 해준다.

 

 

끝지점 변수들이 모두 업데이트되었다면, 해당하는 값들을 모두 더해주면 된다. 하지만, 대각선들중에서 업데이트 되지 않은 변수가 존재할 경우에는 문제가 발생한다.

 

 

대각선을 생각해보면, 수평 벽면에 먼저 접하거나 수직 벽면에 먼저 접할 수 있다. 이 점을 고려해서 코드를 작성한다.

 

 

## 접근방법1 해설코드

---

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
 
    // Complete the queensAttack function below.
    static int queensAttack(int n, int k, int r_q, int c_q, int[][] obstacles) {
        int answer = 0;
        int[][] end = new int[8][2];
        int[][] op = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
        
        // Get End
        for(int i = 0; i < op.length; i++){
            end[i][0] = r_q;
            end[i][1] = c_q;
            
            int rmove = 0;
            int cmove = 0;
            
            if(op[i][0] > 0){
                rmove = n - r_q;      
            }else if(op[i][0] < 0){
                rmove = r_q - 1;
            }
            
            if(op[i][1] > 0){
                cmove = n - c_q;
            }else if(op[i][1] < 0){
                cmove = c_q - 1;
            }
            
            if(i < 4){
                end[i][0] += op[i][0] * Math.max(rmove, cmove);
                end[i][1] += op[i][1] * Math.max(rmove, cmove);
            }else{
                end[i][0] += op[i][0] * Math.min(rmove, cmove);
                end[i][1] += op[i][1] * Math.min(rmove, cmove);         
            }
        }
 
        for(int i = 0; i < obstacles.length; i++){
            for(int j = 0; j < end.length; j++){
                int ro = obstacles[i][0];
                int co = obstacles[i][1];
                
                int re = end[j][0];
                int ce = end[j][1];
                
                if(ro == r_q && re == r_q){
                    // 같은 행
                    if((c_q < co && co < ce) || (c_q > co && co > ce)){
                        end[j][0] = ro - op[j][0];
                        end[j][1] = co - op[j][1];
                    }
                }else if(co == c_q && ce == c_q){
                    // 같은 열
                    if((r_q < ro && ro < re) || (r_q > ro && ro > re)){
                        end[j][0] = ro - op[j][0];
                        end[j][1] = co - op[j][1];
                    }
                }else{
                    // 기울기 비교
                    int dx1 = ro - r_q;
                    int dy1 = co - c_q;
                    int dx2 = re - ro;
                    int dy2 = ce - co;
                    
                    if(dx1 * dy2 == dx2 * dy1){
                        if((r_q < ro && ro < re) || (r_q > ro && ro > re)){
                            if((c_q < co && co < ce) || (c_q > co && co > ce)){
                                end[j][0] = ro - op[j][0];
                                end[j][1] = co - op[j][1];
                            }
                        }    
                    }
                }
            }
        }
 
 
        for(int i = 0; i < 8; i++){
            int mo = 2;
            
            if(i < 4)
                mo = 1;
                
            answer += (Math.abs(end[i][0] - r_q) + Math.abs(end[i][1] - c_q)) / mo;           
        }
        
        return answer;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        String[] nk = scanner.nextLine().split(" ");
 
        int n = Integer.parseInt(nk[0]);
 
        int k = Integer.parseInt(nk[1]);
 
        String[] r_qC_q = scanner.nextLine().split(" ");
 
        int r_q = Integer.parseInt(r_qC_q[0]);
 
        int c_q = Integer.parseInt(r_qC_q[1]);
 
        int[][] obstacles = new int[k][2];
 
        for (int i = 0; i < k; i++) {
            String[] obstaclesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
            for (int j = 0; j < 2; j++) {
                int obstaclesItem = Integer.parseInt(obstaclesRowItems[j]);
                obstacles[i][j] = obstaclesItem;
            }
        }
 
        int result = queensAttack(n, k, r_q, c_q, obstacles);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 

 

 

 

 

## 접근방법2 해설코드

---

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
 
    // Complete the queensAttack function below.
    static int queensAttack(int n, int k, int r_q, int c_q, int[][] obstacles) {
        int u = n + 1, d = 0, left = 0, right = n + 1, ld = 0, lu = n + 1, rd = 0, ru = n + 1;
        int answer =  0;
        
        for(int i = 0; i < obstacles.length; i++){
            int or = obstacles[i][0];
            int oc = obstacles[i][1];
            
            if(r_q == or){
                if(c_q < oc){
                    // RIGHT
                    right = Math.min(right, oc);
                }   
                else{       
                    // LEFT
                    left = Math.max(left, oc);
                }         
            }else if(c_q == oc){
                if(r_q < or){
                    // UP
                    u = Math.min(u, or);
                }else{
                    // DOWN
                    d = Math.max(d, or);
                }
            }else{
                if(or - r_q == oc - c_q){
                    // 기울기 1
                    if(r_q < or){
                        // RIGHT UP
                        ru = Math.min(ru, or);
                    }else{
                        // LEFT DOWN
                        ld = Math.max(ld, or);
                    }
                }else if(or - r_q == -(oc - c_q)){
                    // 기울기 -1
                    if(r_q < or){
                        // LEFT UP
                        lu = Math.min(lu, or);
                    }else{
                        // RIGHT DOWN
                        rd = Math.max(rd, or);
                    }
                }
            }
        }
        
        // UP
        answer += (u - r_q - 1);
        // DOWN
        answer += (r_q - d - 1);
        // LEFT
        answer += (c_q - left - 1);
        // RIGHT
        answer += (right - c_q - 1);
        // RIGHT UP
        answer += Math.min((n + 1) - c_q - 1, ru - r_q - 1);
        // LEFT DOWN
        answer += Math.min(c_q  - 1, r_q - ld - 1);
        // LEFT UP
        answer += Math.min(c_q - 1, lu - r_q - 1);
        // RIGHT DOWN
        answer += Math.min((n + 1) - c_q - 1, r_q - rd - 1);
        
        return answer;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        String[] nk = scanner.nextLine().split(" ");
 
        int n = Integer.parseInt(nk[0]);
 
        int k = Integer.parseInt(nk[1]);
 
        String[] r_qC_q = scanner.nextLine().split(" ");
 
        int r_q = Integer.parseInt(r_qC_q[0]);
 
        int c_q = Integer.parseInt(r_qC_q[1]);
 
        int[][] obstacles = new int[k][2];
 
        for (int i = 0; i < k; i++) {
            String[] obstaclesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
            for (int j = 0; j < 2; j++) {
                int obstaclesItem = Integer.parseInt(obstaclesRowItems[j]);
                obstacles[i][j] = obstaclesItem;
            }
        }
 
        int result = queensAttack(n, k, r_q, c_q, obstacles);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedWriter.close();
 
        scanner.close();
    }
}