[Leetcode]1222. Queens That Can Attack the King

문제 요약

• 알고리즘 분류:  배열, 시뮬레이션, 구현
• 난이도: Medium
• 문제내용:
  • • 8 × 8 체스말이 주어진다. 체스말에서 king 1명, queen N명이 있다.
    • Queem 중에서 왕을 잡을수있는 Queen의 위치들을 반한 하여라
      • 단 앞에 가로 막는 퀸이 있으면  그것은 제외 해야 한다.
• 사이트 주소: https://leetcode.com/problems/queens-that-can-attack-the-king/description/

문제풀이

 이번 문제는 구현 문제중에서 시뮬레이션 문제이다.  각 Queen을 이동 시켜  King까지 갈수 있는지 체크만 하면 되는 문제이다.  일단 퀸이 움직일수있는 방향은 대각선, 가로, 세로 총 8군대이다. 하지만 각 queen이 8방향 탐색하면 시간적으로 비효울이 나와서 반대로 아래 그림처럼 king이 8군대 움직여서 queen을 찾는 방식으로 해야한다.

 여기서 추가로 봐야 하는것은 아래 그림처럼  8방향 탐색 하면서 Queen을 만나고 그 뒤 이어서 탐색 안하고 멈춘다.

구현은 아래와 같이 해주면 된다.

1.  8 × 8 체스판 선언한 다음 각 Queen들 위치를 지정한다.
2. king위치로 부터 각 8방향을 이동한다.
3. 만약 8방향중 queen찾으면 queen위치를 저장하고 멈춘다.

시뮬레이션 구현

 이번 문제에서 핵심은 시뮬레이션 구현 이다. 시뮬레이션에 대한 코드 부분이다.

Python

 # 이동 좌표 설정
dx = [0, 0, -1, 1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, 1, -1, -1, 1]


for i in range(8):
    nx, ny = king

    while(True):
        nx += dx[i]
        ny += dy[i]

        # 범위 안일 경우
        if( 0 <= nx < 8 and 0 <= ny < 8):
            # queen의 위치가 있을경우
            if(boards[nx][ny]):
                result.append([nx, ny])
                break
        else: # 범위 벗어나면 종료한다.
            break

Java

 // 이동 좌표 설정
int[] dx = {0, 0, -1, 1, 1, -1, 1, -1};
int[] dy = {1, -1, 0, 0, 1, -1, -1, 1};

for (int i = 0; i < 8; i++) {
    int nx = king[0];
    int ny = king[1];
    while(true){
        nx += dx[i];
        ny += dy[i];
        // 범위 안일 경우
        if(0 <= nx && nx < 8 && 0 <= ny && ny < 8){
            // queen의 위치가 있을경우
            if(boards[nx][ny]){
                result.add(List.of(nx, ny));
                break;
            }
        }else{ // 범위 벗어나면 종료한다.
            break;
        }
    }
}

 

이번문제는시뮬레이션에 대한 기본적인문제이다. 시뮬레이션에 대한 기본적인 개념만 알면 문제 풀기 쉽다. 전체적인 코드는 아래와 같이 하면된다.

Code

Python

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        boards = [[False] * 8 for _ in range(8)] # 체스말
        result = [] # 결과

        # queen 위치 세팅
        for queen in queens:
            boards[queen[0]][queen[1]] = True

        # 이동 좌표 설정
        dx = [0, 0, -1, 1, 1, -1, 1, -1]
        dy = [1, -1, 0, 0, 1, -1, -1, 1]


        for i in range(8):
            nx, ny = king

            while(True):
                nx += dx[i]
                ny += dy[i]

                # 범위 안일 경우
                if( 0 <= nx < 8 and 0 <= ny < 8):
                    # queen의 위치가 있을경우
                    if(boards[nx][ny]):
                        result.append([nx, ny])
                        break
                else: # 범위 벗어나면 종료한다.
                    break

        return result

Java

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        boolean[][] boards = new boolean[8][8]; // 체스말

        Arrays.stream(boards).forEach(board -> Arrays.fill(board, false));
        List<List<Integer>> result = new ArrayList<>(); // 결과
        // queen 위치 선정
        Arrays.stream(queens).forEach(queen -> {
            int x = queen[0];
            int y = queen[1];
            boards[x][y] = true;
        });

        // 이동 좌표 설정
        int[] dx = {0, 0, -1, 1, 1, -1, 1, -1};
        int[] dy = {1, -1, 0, 0, 1, -1, -1, 1};

        for (int i = 0; i < 8; i++) {
            int nx = king[0];
            int ny = king[1];
            while(true){
                nx += dx[i];
                ny += dy[i];
                // 범위 안일 경우
                if(0 <= nx && nx < 8 && 0 <= ny && ny < 8){
                    // queen의 위치가 있을경우
                    if(boards[nx][ny]){
                        result.add(List.of(nx, ny));
                        break;
                    }
                }else{ // 범위 벗어나면 종료한다.
                    break;
                }
            }
        }

        return result;
    }
}