[backjoon] 17837 새로운 게임 2 java

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

17837번: 새로운 게임 2

구조체 잘 다루는 게 중요한 문제! 삼성 문제는 정말... 구조체 다루기, BFS/DFS, 2차원 배열 돌리기 가 전부인 듯하다...ㅜㅜ

일단 필요한 구조체는 체스판의 색을 관리할 int형태의 이차원 배열
움직이는 말을 관리할 리스트 이차원 배열
말의 정보를 관리할 배열이다
스와 움직이는 말은 정수형태/리스트 형태로 만들어주었다.
 말의 정보는 위치와 방향이 관리되어야하기에 구조체를 만들어서 배열로 만들었다.

게임은 말이 움직이고, 말위의 말들도 같이 움직여줘야한다.
그 안에 방향이 반대방향으로 바뀌고, 내 위치를 찾아서 내 위의 말들 역시 옮겨줘야한다.
위의 말을 같이 움직여주는 것이 이 문제의 포인트인데,
먼저 위치를 찾아준다. 위치는 말이 있는 위치의 배열을 통해 무작정 찾아준다.
그 위치까지 현재 말 위에 있는 모든 말들을 다음 위치로 옮겨준다.
 
쪼개고 쪼개서 무작정 풀면 풀린다...
구조체를 잘 관리하는 것이 중요한 문제ㅠㅠ

import java.io.*;
import java.util.*;
 
class Main {
    static int[][] dirs = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
    static Token[] tokens;
    static int[][] map;
    static LinkedList<Integer>[][] board;
    static int N, K;
    static boolean isFour;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        board = new LinkedList[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                board[i][j] = new LinkedList<>();
            }
        }
        
        tokens = new Token[K];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken()) - 1;
            tokens[i] = new Token(row, col, dir);
            board[row][col].add(i);
        }
        
        isFour = false;
        int T = 0;
        while (T++ < 1000) {
            play();
            if (isFour) break;
        }
        if (T > 1000)
            T = -1;
        System.out.println(T);
    }
 
    // << 말 이동하기 >>
    private static void play() {
        for (int i = 0; i < K; i++) {
            Token nowToken = tokens[i];
            int curD = nowToken.dir;
            int nextR = nowToken.row + dirs[curD][0];
            int nextC = nowToken.col + dirs[curD][1];
 
            if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N || map[nextR][nextC] == 2) {
                curD = changeDir(curD);
                nowToken.dir = curD;
                nextR = nowToken.row + dirs[curD][0];
                nextC = nowToken.col + dirs[curD][1];
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N || map[nextR][nextC] == 2)
                    continue;
            }
 
            move(nowToken, nextR, nextC, i);
        }
    }
    
    // << 현재 말의 높이 찾기 >>
    private static int findHeight(int curIdx) {
        Token now = tokens[curIdx];
        LinkedList<Integer> curBlock = board[now.row][now.col];
        for (int i = 0; i < curBlock.size(); i++) {
            if (curBlock.get(i) == curIdx)
                return i;
        }
        return -1;
    }
 
    // << 말 이동하기 : 현재 말의 높이까지 전체 말을 이동시켜준다. >>
    private static void move(Token nowToken, int nextR, int nextC, int i) {
        int curType = map[nextR][nextC];
        int height = findHeight(i);
        LinkedList<Integer> curBlock = board[nowToken.row][nowToken.col];
        while(curBlock.size() > height) {
            int nextIdx = -1;
            if(curType == 0) {
                nextIdx = curBlock.remove(height);
            }else {
                nextIdx = curBlock.removeLast();
            }
            board[nextR][nextC].add(nextIdx);
            tokens[nextIdx].row = nextR;
            tokens[nextIdx].col = nextC;
        }
        if(board[nextR][nextC].size() > 3) isFour = true;
    }
 
    private static int changeDir(int curD) {
        if (curD == 0)
            return 1;
        if (curD == 1)
            return 0;
        if (curD == 2)
            return 3;
        if (curD == 3)
            return 2;
        return 0;
    }
 
    static class Token {
        int row;
        int col;
        int dir;
 
        Token(int row, int col, int dir) {
            this.row = row;
            this.col = col;
            this.dir = dir;
        }
    }
}