백준 17837 새로운 게임2 자바(java)

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

 

풀이 방법

구현, 시뮬레이션 문제이다. 

체스 말은 ChessMan 이라는 클래스를 만들어 좌표와 이동 방향을 저장하고 객체로 관리하도록 하였다.

 

1. 1번 ~ K번 말을 담을 수 있는 ChessMan 배열을 생성하여 객체를 저장한다.

2. 리스트 ArrayList<Integer> 타입을 담을 수 있는 2차원 배열을 생성하여 각 좌표마다 리스트에 말 번호를

    저장하여 관리하도록 한다.

3. 말을 1번부터 이동시키는 데, 말이 있는 좌표의 말 리스트에서 해당 말과 그 위에 있는 말들을 모두

    moves 리스트에 삽입한다.

4. 방향에 따라 이동한 좌표의 칸이 범위를 벗어나거나 파란색이면 방향을 바꾼다.

    방향을 바꾼 뒤 이동한 칸도 범위를 벗어나거나 파란색이라면 이동하지 않는다.

5. 이동할 칸이 흰색이면 moves 배열의 말 번호를 앞에서부터 순차적으로 해당 좌표의 말 리스트에

    삽입하고 이때, 말 객체 배열에서 이동시키는 말 객체의 x, y 좌표를 갱신해준다.

6. 이동할 칸이 빨간색이면 원래 쌓여있는 순서의 반대로 쌓아야 하므로 moves 배열을 뒤에서부터 순회하여

    5번과 같은 방식으로 해당 좌표의 말 리스트에 삽입해준다.

7. 이동 후엔 원래 말이 있던 좌표의 리스트에서 이동시킨 말들의 번호를 제거한다.

8. 이동시킨 칸의 말 리스트 크기가 4이상이면 바로 턴을 종료한다.

 

 

코드

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

public class Main {

    static class ChessMan {
        int x;
        int y;
        int d;

        public ChessMan(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    static int N;
    static int K;
    static int[][] board;
    static ArrayList<Integer>[][] list;
    static ChessMan[] chessMen;
    static int[] dx = {0, 0, 0, -1, 1};
    static int[] dy = {0, 1, -1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        board = new int[N+1][N+1];
        list = new ArrayList[N+1][N+1];
        chessMen = new ChessMan[K+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                list[i][j] = new ArrayList<>();
            }
        }

        for(int i=1; i<=K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            chessMen[i] = new ChessMan(x, y, d);
            list[x][y].add(i);
        }

        int t = 0;
        boolean isEnd = false;
        while(++t <= 1000) {
            if(!moveHorses()) {
                isEnd = true;
                break;
            }
        }

        if(isEnd) {
            System.out.println(t);
        } else {
            System.out.println(-1);
        }
    }

    public static boolean moveHorses() {
        for(int i=1; i<=K; i++) {
            ChessMan chessMan = chessMen[i];
            ArrayList<Integer> moves = new ArrayList<>(); // 이동할 말들
            int x = chessMan.x;
            int y = chessMan.y;

            // 위에 있는 말들 구하기
            int pos = list[x][y].size();
            for(int j=0; j<list[x][y].size(); j++) {
                if(list[x][y].get(j) == i) {
                    pos = j; // 시작 위치
                }
                if(j >= pos) {
                    moves.add(list[x][y].get(j));
                }
            }
            // 이동할 좌표
            int nx = x + dx[chessMan.d];
            int ny = y + dy[chessMan.d];
            // 경계를 벗어나거나 파란색 칸이면 방향 바꾸기
            if(nx < 1 || nx > N || ny < 1 || ny > N || board[nx][ny] == 2) {
                chessMan.d = (chessMan.d % 2 != 0) ? chessMan.d + 1 : chessMan.d - 1;
                nx = x + dx[chessMan.d];
                ny = y + dy[chessMan.d];
                if(nx < 1 || nx > N || ny < 1 || ny > N || board[nx][ny] == 2) { // 이동 불가
                    continue;
                }
            }

            if(board[nx][ny] == 0) { // 흰색인 경우
                for(Integer num : moves) {
                    list[nx][ny].add(num);
                    chessMen[num].x = nx;
                    chessMen[num].y = ny;
                }
            } else if(board[nx][ny] == 1) { // 빨간색인 경우
                for(int j=moves.size()-1; j>=0; j--) {
                    list[nx][ny].add(moves.get(j));
                    chessMen[moves.get(j)].x = nx;
                    chessMen[moves.get(j)].y = ny;
                }
            }

            // 원래 있던 곳에선 말 제거
            for(int j=list[x][y].size()-1; j>=pos; j--) {
                list[x][y].remove(j);
            }

            // 말이 4개 이상 쌓이면 종료
            if(list[nx][ny].size() >= 4) {
                return false;
            }
        }
        return true;
    }
}