[리트코드] 1222번 - JAVA

https://leetcode.com/problems/queens-that-can-attack-the-king/submissions/

Queens That Can Attack the King - LeetCode

---

문제를 풀기위해 했던 생각들을 정리해보자!

 

• Queen은 오로지 직진만 가능하다 - 가로, 세로, 대각선
• 만약 다른 Queen에 의해 block되어 있다면 King을 공격할 수 있다
• King 기준으로 가로, 세로, 대각선을 검사해서 근접한 Queen들만 출력하면 되지 않을까?! (핵심!)
• 이를 위해 dx, dy 선언 - 이동 인덱스
• 이동할 수 있는 라인은 위, 아래, 왼쪽, 오른쪽, 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래 이다
• 만약 같은 라인에 퀸을 찾았다면 flag를 통해 더이상 같은 라인의 퀸을 찾지 않는다

 

 

자바 코드)

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
    
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> answer = new ArrayList<>();
        int[][] q = new int[8][8];
        int x = king[0];
        int y = king[1];
        int nx, ny;
        
        for(int i=0;i<queens.length;i++) { //탐색하기 쉽도록 queens 위치 저장
            q[queens[i][0]][queens[i][1]] = 1;
        }
        
        for(int i=0;i<8;i++) { //위, 아래, 왼, 오, 왼위, 왼아, 오위, 오아 순대로 탐색
            nx = x;
            ny = y;
            Boolean flag = false;
            while(true) {
                if(flag == true) {
                    break;
                }
                nx += dx[i];
                ny += dy[i];
                if(nx<0 || nx>=8 || ny<0 || ny>=8) {
                    break;
                }
                if(q[nx][ny] == 1) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nx);
                    tmp.add(ny);
                    answer.add(tmp);
                    flag = true;
                }
            }
        }
        
        
        return answer;
    }
}

 

 

효율성...은 모르겠고 일단 통과는 하더라