Queen’s Attack II

문제: Queen’s Attack II

난이도: Medium

 

문제 설명

 체스 판에 퀸이 하나, 장애물이 없거나 있을 경우 퀸이 몇 칸을 공격할 수 있는지를 구하여라.

 주어지는 정보는 체스 판의 가로(세로)길이 n, 장애물의 수 k, 퀸의 위치인 r_q(행 위치)와 c_q(열 위치), 장애물들의 위치(행, 열)가 있다.

 예를 들어, 체스 판의 크기가 5 x 5, 퀸의 위치가 (4, 3), 장애물이 3개이고 위치는 각각 (5, 5), (4, 2), (2, 3)이면 다음과 같은 상황이다.

따라서 이 경우의 답은 10이다.

 

문제 해결

소스 코드

	static int queensAttack(int n, int k, int r_q, int c_q, int[][] obstacles) {
        int sr = r_q;
        int sc = c_q;
        int cnt = 0;
        int rotDir = 0;
        int[][] checkedObs = {{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}};

        int obsIdx = -1;
        for(int i = 0; i < obstacles.length; i++) { // 유효한 장애물 체크{r, c}
            if(obstacles[i][0]>r_q && obstacles[i][1]==c_q) {
                obsIdx = 0;
            } else if(obstacles[i][0]<r_q && obstacles[i][1]==c_q) {
                obsIdx = 4;
            } else if(obstacles[i][0]==r_q && obstacles[i][1]>c_q) {
                obsIdx = 2;
            } else if(obstacles[i][0]==r_q && obstacles[i][1]<c_q) {
                obsIdx = 6;
            } else if(Math.abs(obstacles[i][0]-r_q)==Math.abs(obstacles[i][1]-c_q)) {
                int rn = obstacles[i][0]-r_q;
                int cn = obstacles[i][1]-c_q;
                if(rn>0&&cn>0) {
                    obsIdx = 1;
                } else if(rn>0&&cn<0) {
                    obsIdx = 7;
                } else if(rn<0&&cn>0) {
                    obsIdx = 3;
                } else if(rn<0&&cn<0) {
                    obsIdx = 5;
                }
            }
            if(obsIdx == -1)
                continue;
            if((Math.abs(checkedObs[obsIdx][0]-r_q)+Math.abs(checkedObs[obsIdx][1]-c_q))>(Math.abs(obstacles[i][0]-r_q)+Math.abs(obstacles[i][1]-c_q))||(checkedObs[obsIdx][0]==0&&checkedObs[obsIdx][1]==0)) {
                checkedObs[obsIdx][0] = obstacles[i][0];
                checkedObs[obsIdx][1] = obstacles[i][1];
            }
            obsIdx = -1;
        }
        while(rotDir < 8) { // 공격 가능한 칸 수 체크
            for(int i = 0; i < (n-1); i++) {
                switch(rotDir) {
                    case 0: sr++; break;
                    case 1: sr++; sc++; break;
                    case 2: sc++; break;
                    case 3: sr--; sc++; break;
                    case 4: sr--; break;
                    case 5: sr--; sc--; break;
                    case 6: sc--; break;
                    case 7: sr++; sc--; break;
                }
                if(sr==checkedObs[rotDir][0] && sc==checkedObs[rotDir][1]) {
                    break;
                }
                if(sr<1||sr>n||sc<1||sc>n) {
                    break;
                }
                cnt++;
            }
            sr = r_q;
            sc = c_q;
            rotDir++;
        }
        return cnt;
    }

 

 

해설

 문제 해결을 위해 가장 먼저 한 일은 유효한 장애물 찾기다. 장애물들이 여럿 있어도 모두가 퀸의 길을 가로막지는 않기 때문이다. 퀸이 이동할 수 없는 위치에 있는 장애물이나 이미 한 장애물 때문에 막힌 경로에 있는 장애물은 유효하지 않다.

 그 후 퀸이 공격할 수 있는 칸수를 세기 위해 퀸의 위치에서 시작해 밖으로 뻗어나가는 방향으로 총 8가지의 방향으로 한 칸씩 수를 센다. 수를 세다가 체스 판을 벗어나거나 장애물을 만나면 그 방향의 수를 세는 것을 중단하고 다음 방향으로 퀸의 위치에서 수를 계속 센다.