16920번 : 확장 게임 [JAVA]

문제 링크

성공 여부(걸린 시간): 실패(1시간)

아이디어

처음에는 모든 플레이어의 성 좌표를 리스트에 저장해두고, 라운드마다 그 좌표들에서 BFS를 돌려서 확장하려 했다.
하지만 이 방식은 같은 턴 안에서 새로 점령한 칸을 경유하지 못하는 문제가 있었고, 이미 점령된 내부 칸까지 계속 BFS를 돌리다 보니 시간도 비효율적이었다.

핵심은 플레이어별 프런티어 큐(frontier queue) 를 유지하는 것이다.

• 각 플레이어는 현재 확장할 수 있는 가장자리 칸만 큐에 넣어둔다.
• 자기 턴이 되면, 큐에서 꺼낸 칸들만 기준으로 최대 Sᵢ층까지 BFS를 진행한다.
• 이렇게 하면 같은 턴 안에서 새로 점령한 칸을 경유할 수 있고, 불필요한 내부 칸 탐색도 하지 않게 된다.

결과적으로 모든 칸은 최대 한 번만 큐에 들어가기 때문에, 전체 시간 복잡도는 O(NM) 수준이 된다.

풀이 코드

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

public class Main {
    static int N, M, P;
    static int[] S;                 // 각 플레이어의 최대 확장 거리
    static char[][] board;
    static boolean[][] visited;     // 점령/벽 여부
    static ArrayDeque<int[]>[] q;   // 플레이어별 프런티어 큐
    static int[] ans;               // 플레이어별 점령 칸 수

    static final int[] dx = {1, 0, -1, 0};
    static final int[] dy = {0, 1, 0, -1};

    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());
        M = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        S = new int[P + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= P; i++) S[i] = Integer.parseInt(st.nextToken());

        board = new char[N][M];
        visited = new boolean[N][M];
        q = new ArrayDeque[P + 1];
        ans = new int[P + 1];
        for (int i = 1; i <= P; i++) q[i] = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = line.charAt(j);
                board[i][j] = c;
                if (c == '#') {
                    visited[i][j] = true;             // 벽
                } else if (c == '.') {
                    // 빈칸
                } else { // '1'..'9'
                    int p = c - '0';
                    visited[i][j] = true;             // 성
                    q[p].add(new int[]{i, j});        // 프런티어 초기화
                    ans[p]++;                         // 성 개수 반영
                }
            }
        }

        boolean progressed = true;
        while (progressed) {
            progressed = false;

            // 플레이어 1 → P 순서대로 차례 진행
            for (int p = 1; p <= P; p++) {
                for (int step = 0; step < S[p]; step++) {
                    int layerSize = q[p].size();
                    if (layerSize == 0) break;

                    for (int t = 0; t < layerSize; t++) {
                        int[] cur = q[p].poll();
                        int x = cur[0], y = cur[1];

                        for (int dir = 0; dir < 4; dir++) {
                            int nx = x + dx[dir], ny = y + dy[dir];
                            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                            if (visited[nx][ny]) continue;
                            if (board[nx][ny] != '.') continue; // 빈칸만 확장 가능

                            visited[nx][ny] = true;
                            board[nx][ny] = (char) ('0' + p);
                            q[p].add(new int[]{nx, ny});
                            ans[p]++;
                            progressed = true;
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= P; i++) {
            if (i > 1) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb);
    }
}