BOJ 16920, 확장게임

코딩테스트를 자바로 연습하기 위해서 요즘 자바로 문제를 풀고있다.

풀이과정

우선 문제를 요약해보자면 플레이어 Player 1 ~ P까지 순서대로 자신의 성을 확장시켜 나가는 게임이다.
자신의 차례에는 자신이 움직일 수 있는 칸의 갯수만큼 움직일 수 있고 다른사람이 이미 확장한 칸에는 성을 확장시킬 수 없다.

문제를 풀기 위해서 Queue 배열을 생성해주었다. 이 큐 배열이 하는 역할은 다음 자신의 차례에 확장할 성의 정보를 담는다.
이전에 움직였던 성은 더이상 이동할 필요가 없기 때문에 이 큐배열에 넣지 않는다.

한가지 애를 먹었던 점은 자바는 c++과 다르게 LinkedList[] q = new LinkedList[10]; 으로 선언하는것이 끝이 아니라 각 배열의 요소들을 또 초기화 시켜주어야 한다.
따라서 for(int i=0; i<10; i++) q[i] = new LinkedList();를 추가로 해주어야한다.

package Algorithm.day9;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class P2{
    static int N, M, P;
    static int[] step = new int[10];
    static boolean[][] canExtend = new boolean[1001][1001];
    static ArrayList<LinkedList<Tuple>> q = new ArrayList<>(11);
    static int[] area = new int[11];
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};

    static class Tuple{
        int x,y,z;
        Tuple(int x, int y, int z){
            this.x =x;
            this.y = y;
            this.z = z;
        }
    }
    public static void main(String[] args) throws IOException {
        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());

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

        for(int i=1; i<=P+1; i++){
            q.add(new LinkedList<>());
        }

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                char ch = str.charAt(j);
                if(ch == '.') canExtend[i][j] = true;
                else if(ch == '#') canExtend[i][j] = false;
                else{
                    canExtend[i][j] = false;
                    LinkedList l = q.get(ch-'0');
                    l.offer(new Tuple(i, j, 0));
                    q.set(ch - '0', l);
                    area[ch-'0'] += 1;
                }
            }
        }

        while(true){
            boolean isExtend = false;

            for(int i=1; i<=P; i++){
                LinkedList<Tuple> nq = new LinkedList<>();
                LinkedList<Tuple> cq = q.get(i);
                while(!cq.isEmpty()){
                    Tuple tuple = cq.poll();
                    int cx = tuple.x;
                    int cy = tuple.y;
                    int cz = tuple.z;
                    if(cz >= step[i]){
                        nq.offer(new Tuple(cx, cy, 0));
                        continue;
                    }
                    for(int dir = 0; dir < 4; dir++){
                        int nx = cx + dx[dir];
                        int ny = cy + dy[dir];
                        int nz = cz + 1;
                        if(nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                        if(canExtend[nx][ny] == false) continue;
                        cq.offer(new Tuple(nx, ny, nz));
                        canExtend[nx][ny] = false;
                        area[i]++;
                        isExtend = true;
                    }
                }
                q.set(i, nq);
            }
            if(!isExtend) break;
        }

        for(int i=1; i<=P; i++){
            System.out.print(area[i] + " ");
        }

    }
}