[Java] 16920 확장게임

문제

문제
구사과와 친구들이 확장 게임을 하려고 한다.
이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 
각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다.
한 칸 위에 성이 두 개 이상인 경우는 없다.

게임은 라운드로 이루어져 있고, 
각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다.

제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 
이런 식으로 라운드가 진행된다.

각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다.
플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 

위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 
벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 

성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.

모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다.
게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.

입력
첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 
둘째 줄에는 S1, S2, ...SP가 주어진다.

다음 N개의 줄에는 게임판의 상태가 주어진다.
'.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.

모든 플레이어는 적어도 하나의 성을 가지고 있으며,
게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.

출력
플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.

문제 풀이

BFS를 활용해야하는 문제이다.

처음에는 큐 하나에 사람들의 성 위치를 차례로 넣고 사람당 큐에서 위치를 꺼내 이동할 수 있는 move 값만큼 dc,dr 방향으로 이동해주는 방향으로 풀었는데 도중에 방향을 꺾어서 계산할 수 있다는 점을 간과한 나머지 틀린 답안이 되었다. 하나의 큐에 모든 플레이어의 좌표를 넣어서 계산하고 있었기 때문에 수정하기가 힘들었다.

그래서 플레이어가 9명밖에 안된다는 점을 활용해 플레이어별로 큐를 생성해서 각자 저장을 하고 라운드별로 플레이어 하나씩 큐를 비우는 방식으로 변경하여 값을 처리했다. 자세한 과정은 주석으로 달아 설명한다.

틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int n, m, p;
    private static int[] move;
    private static String[][] map;
    private static List<Pos>[] start;
    private static int[] count;

    private static final int[] dr = {-1, 1, 0, 0};
    private static final int[] dc = {0, 0, -1, 1};
    public static class Pos{
        private final int x;
        private final int y;
        private final int p;

        public Pos(int x, int y, int p) {
            this.x = x;
            this.y = y;
            this.p = p;
        }

        public int getX(){
            return x;
        }

        public int getY() {
            return y;
        }

        public int getP(){
            return p;
        }
    }
    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());

        map = new String[n][m];
        move = new int[p + 1];
        count = new int[p + 1];
        start = new ArrayList[p + 1];
        for(int i = 0; i < start.length; i++){
            start[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i < p + 1; i++)
            move[i] = Integer.parseInt(st.nextToken());

        for(int i = 0; i < n; i++){
            String[] sp  = br.readLine().split("");
            for(int j = 0; j < m; j++) {
                map[i][j] = sp[j];
                if(!map[i][j].equals(".") && !map[i][j].equals("#")){
                    start[Integer.parseInt(map[i][j])].add(new Pos(i,j, Integer.parseInt(map[i][j])));
                    count[Integer.parseInt(map[i][j])]++;
                }
            }
        }

        bfs();

        for(int i = 1; i < count.length; i++)
            System.out.print(count[i] + " ");
    }

    public static void bfs(){
        Queue<Pos> q = new LinkedList<>();
        for (List<Pos> pos : start) {
            q.addAll(pos);
        }

        while(!q.isEmpty()) {
            Pos now = q.poll();
            int pm = now.getP();
            for (int i = 0; i < 4; i++) {
                for (int j = 1; j <= move[pm]; j++) {
                    int nx = now.getX() + (dr[i] * j);
                    int ny = now.getY() + (dc[i] * j);

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                        break;
                    }

                    if (!map[nx][ny].equals("."))
                        break;

                    map[nx][ny] = map[now.getX()][now.getY()];
                    count[pm]++;

                    q.add(new Pos(nx, ny, pm));
                }
            }
        }
    }
}

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class N16920 {
    private static int n, m, p;
    private static String[][] map;
    private static final int[] dr = {-1, 1, 0, 0};
    private static final int[] dc = {0, 0, -1, 1};
    public static class Pos{
        private final int x;
        private final int y;

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

        public int getX(){
            return x;
        }

        public int getY() {
            return y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // map의 크기, 사람 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        p = Integer.parseInt(st.nextToken());

        // 맵, 플레이어별 최대 이동 수, 플레이어별 성의 갯수 저장 배열 초기화
        map = new String[n][m];
        int[] move = new int[p + 1];
        int[] count = new int[p + 1];
        
        // 플레이어별 큐와 초기 성 위치 값 저장 리스트
        Queue<Pos>[] qlist = new LinkedList[p + 1];
        List<Pos>[] start = new ArrayList[p + 1];
        for(int i = 0; i < p + 1; i++){
            start[i] = new ArrayList<>();
            qlist[i] = new LinkedList<>();
        }

        // 플레이어별 최대 이동 수 입력
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i < p + 1; i++)
            move[i] = Integer.parseInt(st.nextToken());

        // map 입력
        for(int i = 0; i < n; i++){
            String[] sp  = br.readLine().split("");
            for(int j = 0; j < m; j++) {
                map[i][j] = sp[j];
                // 플레이어 성 위치를 입력받았을 경우 해당 위치를 해당 플레이어 큐에 저장하고 성 개수를 +1
                if(!map[i][j].equals(".") && !map[i][j].equals("#")){
                    qlist[Integer.parseInt(map[i][j])].offer(new Pos(i,j));
                    count[Integer.parseInt(map[i][j])]++;
                }
            }
        }

        // 성을 확장할 플레이어의 번호와 해당 라운드에서 확장된 성의 갯수
        int player = 1;
        int round = 0;
        // 라운드를 돌아가면서 성의 갯수를 카운트한다.
        while(true) {
            // 플레이어별 확장한 성의 갯수
            int expandCount = bfs(qlist[player], move[player], player);
            // 확장한 성 갯수만큼 총 갯수와 라운드에서 확장된 성의 갯수를 늘려준다.
            count[player] += expandCount;
            round += expandCount;

            // 다음 플레이어의 턴을 위해 +1
            player++;
            
            // 모든 플레이어가 한 라운드를 돌았을 경우
            if(player == p + 1){
                // 확장된 성의 갯수가 0개이면 종료
                if(round == 0)
                    break;
                
                // 라운드별 확장 수와 플레이어 턴을 초기화
                round = 0;
                player = 1;
            }
        }
        
        // 결과 출력
        for(int i = 1; i < count.length; i++)
            System.out.print(count[i] + " ");
    }

    public static int bfs(Queue<Pos> q, int maxMove, int player){
        // 확장된 성 갯수, 현재 이동한 횟수
        int expandCount = 0;
        int move = 1;

        // 큐가 빌때까지 실행
        while(!q.isEmpty()) {
            int size = q.size();

            // 현재 해당 플레이어의 성 갯수만큼 반복한다.
            for(int i = 0 ; i < size ; ++i) {
                Pos cur = q.poll();
                
                // 성 위치의 상하좌우를 확인
                for(int j = 0 ; j < 4 ; ++j) {
                    int nr = cur.getX() + dr[j];
                    int nc = cur.getY() + dc[j];
                    
                    // map 범위를 벗어나면 생략
                    if(nr < 0 || nr >= n || nc < 0 || nc >= m)
                        continue;
                    
                    // 빈 곳을 찾았으면 해당 위치를 큐에 넣고 플레이어가 해당 위치를 점령
                    // 확장된 성 갯수 +1
                    if(map[nr][nc].equals(".")) {
                        q.offer(new Pos(nr, nc));
                        map[nr][nc] = player + "";
                        expandCount++;
                    }
                }
            }
            // 이동한 횟수 +1
            move++;

            // 이동한 횟수가 최대 이동 가능 수를 넘으면 종료
            if(move > maxMove)
                break;
        }

        // 확장한 성의 갯수를 리턴
        return expandCount;
    }
}