[백준/Java] 16920번 확장 게임

-Code

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

public class BOJ16920 {
    static class PosInfo {
        int player, row, col;

        public PosInfo(int player, int row, int col) {
            this.player = player;
            this.row = row;
            this.col = col;
        }
    }
    static int rowSize;
    static int colSize;
    static int[][] board;
    static boolean[][] visted;
    static int[] playersStep;
    // 이동 방향
    static int[] dRow = {-1, 0, 1, 0};
    static int[] dCol = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        rowSize = Integer.parseInt(st.nextToken());
        colSize = Integer.parseInt(st.nextToken());
        int playerCnt = Integer.parseInt(st.nextToken());
        // visited setting
        visted = new boolean[rowSize][colSize];
        // 각 플레이어의 스텝 받기
        st = new StringTokenizer(br.readLine());
        playersStep = new int[playerCnt + 1];
        for (int player = 1; player <= playerCnt; player++) {
            playersStep[player] = Integer.parseInt(st.nextToken());
        }
        // board and posList setting
        ArrayList<PosInfo> playersPos = new ArrayList<>();
        board = new int[rowSize][colSize];
        for (int r = 0; r < rowSize; r++) {
            String line = br.readLine();
            for (int c = 0; c < colSize; c++) {
                char ch = line.charAt(c);
                int change;
                // 플레이어면 플레이어 저장 및 숫자 저장
                if (ch != '#' && ch != '.') {
                    change = (ch - '0');
                    playersPos.add(new PosInfo(change, r, c));
                } else {
                    // 벽이나 빈 공간인 경우 빈공간은 0 벽이면 -1
                    change = ch == '.' ? 0 : -1;
                }
                board[r][c] = change;
            }
        }
        // 출력
        StringBuilder sb = new StringBuilder();
        int[] answer = getGameResult(playersPos, playerCnt);
        for (int i = 1; i <= playerCnt; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.println(sb);
    }

    private static int[] getGameResult(ArrayList<PosInfo> playersPos, int playerCnt) {
        int[] answer = new int[playerCnt + 1];
        // visited, deque 셋팅
        ArrayDeque<PosInfo>[] playerDeq = new ArrayDeque[playerCnt + 1];
        for (int i = 0; i <= playerCnt; i++) {
            playerDeq[i] = new ArrayDeque<>();
        }
        for (PosInfo player : playersPos) {
            visted[player.row][player.col] = true;
            answer[player.player]++;
            playerDeq[player.player].add(player);
        }
        // 탐색
        while (true) {
            boolean isMove = false;
            // 각 플레이서 순서대로 각 덱을 바탕으로 탐색
            for (int p = 1; p <= playerCnt; p++) {
                // 스텝 만큼 반복
                for (int s = 0; s < playersStep[p]; s++) {
                    // 스텝 횟수 만큼 size를 계산해 확장
                    int deqSize = playerDeq[p].size();
                    // 사이즈 없으면 바로 탈출
                    if (deqSize == 0) break;
                    for (int t = 0; t < deqSize; t++) {
                        PosInfo now = playerDeq[p].pollFirst();
                        // 상하좌우 탐색
                        for (int i = 0; i < 4; i++) {
                            int nextRow = now.row + dRow[i];
                            int nextCol = now.col + dCol[i];
                            // 이동 가능하고 방문하지 않은 경우
                            if (canMove(nextRow, nextCol) && !visted[nextRow][nextCol]) {
                                visted[nextRow][nextCol] = true;
                                answer[now.player]++;
                                playerDeq[now.player].addLast(new PosInfo(now.player, nextRow, nextCol));
                                isMove = true;
                            }
                        }
                    }
                }
            }
            // 이동할 곳 없으면 탈출
            if (!isMove) {
                break;
            }
        }

        return answer;
    }
    // 이동 가능한지 확인
    private static boolean canMove(int row, int col) {
        return (0 <= row  && row < rowSize) &&
                (0 <= col && col < colSize) &&
                (board[row][col] == 0);
    }
}

처음에 무조건 1걸음씩 이동하는 줄 알고 문제 로직을 짰습니다. 하지만 알고 보니 주어진 step만큼 이동을 하는 것이었습니다. 그래서 이 것과 deque를 배열로 두고 스텝만큼 반복하라는 힌트를 받고 다시 짰습니다. 그렇게 짰으나 탈출 조건을 모든 덱을 검사하는 비효율 적인 방법을 사용해서 flag 사용으로 바꾸고 size가 0인 경우에도 검색해서 시간 초과 문제가 생겨서 이 부분도 수정해서 해결했습니다.