문제 탐색하기

입력 자료 정리

1. n은 체스판의 크기, k는 말의 개수다
2. 이어서 들어오는 n x n의 값은 각 체스판의 색이다
   0은 흰색, 1은 빨간색, 2는 파란색이다
3. k개의 입력값은 각각 y좌표, x좌표, 방향이다
   방향은 우:1, 좌:2, 상:3, 하:4이다

해결방법 추론

1. n과 k가 작고 특정 횟수 이상을 넘어갈 경우 종료하는데 1000번을 넘지 않으므로 간단하게 구현 + 시뮬레이션 문제라고 생각했다
2. 주어진 조건에 맞춰서 구현만 잘 하면 되는 문제다
3. 다만 몇가지 생각할 것이 말을 쌓아올려야하기 때문에, 이때의 자료구조를 선택해야한다
4. 이때 자료구조는 덱과 리스트 중 고민했는데, 한번 뒤집어야하기 때문에 리스트를 선택했다
   리스트 2차원 배열을 자료구조로 선택한다면 쉽게 관리할 수 있을 것이다

시간복잡도 계산

1. n^2만큼 체스판을 돌고, k개의 말을 모두 움직이며 이것을 1천번까지 반복한다
   시간복잡도는 O(time x k x n^2)인데 최댓값으로 계산하면 12 x 10 x 1000이므로 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 간단한 크기 입력값들은 int형 변수에 관리한다
2. 체스판의 색깔은 int형 2차원 배열 arr에 저장했으며, 그 칸에 있는 체스말을 확인하기 위해 리스트 2차원 배열도 똑같은 n x n크기로 선언했다
3. 이어서 말들의 상태를 관리하기 위해 Knight 클래스를 선언하고 해당 타입의 1차원 배열을 선언해서 입력값을 받아 관리하도록 했다
4. Knight클래스는 방향과 현재 좌표 정보를 갖는다.
5. 정답 출력을 위한 ans도 0으로 초기화했다

구현 코드 설계

1. ans를 1000번 이하까지 반복하며 증가시키도록 설계했다.
2. 이 시뮬레이션 동안 주어진 조건대로 진행하며, 만약 말이 한 체스판에 4개 이상있는 경우 종료한다.

말을 움직이는 단계

1. 미리 방향에 따라 좌표를 움직이도록 dy, dx 배열을 선언했다. 이것을 이용해서 각 knight의 이동했을 때의 좌표를 변수로 관리한다

범위를 벗어낫거나 파란색일 경우

1. 만약 범위를 벗어낫거나 파란색일 경우 방향을 반대로 바꿔준다
2. 이후 다시 해당 방향으로 이동한 다음 똑같이 검증을 진행한다
3. 범위를 벗어나지 않았고, 파란색일 경우, 빨간색과 흰색일때와 똑같이 진행한다

그외의 경우

1. 범위를 벗어나지 않고 빨간색과 흰색일 때는 정상적으로 말을 이동시킨다

말의 위치를 변화시키는 단계

1. 먼저 현재 이동하려는 말과 위에 있는 말들을 보관한 임시 리스트를 선언한다
2. 그리고 움직이기 전의 위치에 있는 말들을 순회하면서 이동하려는 말과 위의 말들을 임시 리스트에 넣어준다
3. 이어서 빨간색과 흰색을 구분하는 check를 통해 만약 빨간색일 경우 임시배열을 뒤집어준다
4. 그 다음 이동전의 위치에 있는 이동하려는 말과 그 이후 말들을 모두 제거한다
5. 그리고 임시 배열의 말들의 현재 위치를 이동하려는 위치로 바꿔주며, 해당 위치의 말들을 관리하는 리스트 배열도 갱신해준다

종료조건을 충족시키는지 확인하는 단계

1. 말을 하나 움직일때마다 종료조건을 확인해야한다
2. 모든 칸을 순회하면서 만약 한칸이라도 4개 이상의 말을 가지고 있으면 메소드를 종료시킨다

출력값 설계

1. 완성한 ans를 출력하는데 만약 1000이상일 경우 -1로 바꿔준다
2. 1번 예외상황을 고려해서 출력하면 정답이 된다

정답 코드

import java.io.*;
import java.util.*;


class Knight{
    int nowY;
    int nowX;
    int dir;
    Knight(int y, int x, int d){
        this.nowY = y;
        this.nowX = x;
        this.dir = d;
    }
}


public class Main {


    static int[][] arr;
    static int n;
    static int k;
    static Knight[] knights;
    static int[] dy = {0,0,0,-1,1};
    static int[] dx = {0, 1,-1,0,0};
    static List<Integer>[][] lists;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = new int[n+1][n+1];
        lists = new ArrayList[n+1][n+1];
        for (int i = 1; i < n+1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n+1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                lists[i][j] = new ArrayList<>();
            }
        }

        knights = new Knight[k+1];
        for (int i = 1; i < k+1; i++) {
            st = new StringTokenizer(br.readLine());
            knights[i] = new Knight(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            lists[knights[i].nowY][knights[i].nowX].add(i);
        }
        int ans = 0;
        while(ans <= 1000){
            ans++;
            if(moves()){
                break;
            }
        }

        if(ans > 1000){
            ans = -1;
        }
        bw.write(ans+"");
        br.close();
        bw.close();
    }

    private static boolean moves() {
        for (int i = 1; i < k+1; i++) {
            Knight knight = knights[i];
            int ny = knight.nowY + dy[knight.dir];
            int nx = knight.nowX + dx[knight.dir];
            if(!isRange(ny, nx) || arr[ny][nx] == 2){
                knights[i].dir = change(knight.dir);
                int nny = knights[i].nowY + dy[knights[i].dir];
                int nnx = knights[i].nowX + dx[knights[i].dir];
                if(isRange(nny, nnx) && arr[nny][nnx] != 2){
                    if(arr[nny][nnx] == 0){
                        removes(knight.nowY, knight.nowX, nny, nnx, i, false);
                    }else{
                        removes(knight.nowY, knight.nowX, nny, nnx, i, true);
                    }
                }
            }else if(isRange(ny, nx)){
                if(arr[ny][nx] == 0){
                    removes(knight.nowY, knight.nowX, ny, nx, i, false);
                }else if(arr[ny][nx] == 1){
                    removes(knight.nowY, knight.nowX, ny, nx, i, true);
                }
            }

            if(finish()){
                return true;
            }

        }
        return false;
    }

    private static void removes(int py, int px, int ny, int nx, int num, boolean check) {
        int size = lists[py][px].size();
        boolean isOk = true;
        List<Integer> tmp = new ArrayList<>();
        int now = 0;
        for (int i = 0; i < size; i++) {
            if(lists[py][px].get(i) == num){
                now = i;
                isOk = false;
            }
            if(!isOk){
                tmp.add(lists[py][px].get(i));
            }
        }
        if(check){
            Collections.reverse(tmp);
        }
        for (int i = now; i < size; i++) {
            lists[py][px].remove(now);
        }
        for (int i = 0; i < tmp.size(); i++) {
            knights[tmp.get(i)].nowY = ny;
            knights[tmp.get(i)].nowX = nx;
            lists[ny][nx].add(tmp.get(i));
        }
    }

    private static boolean finish() {
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if(lists[i][j].size() >= 4){
                    return true;
                }
            }
        }
        return false;
    }

    private static int change(int dir) {
        switch(dir) {
            case 1:
                return 2;
            case 2:
                return 1;
            case 3:
                return 4;
            case 4:
                return 3;
        }
        return -1;
    }

    private static boolean isRange(int ny, int nx) {
        if(ny>0 && ny<=n && nx>0 && nx<=n){
            return true;
        }
        return false;
    }
}

문제 링크

17837번 - 새로운 게임 2