BOJ_16920_확장 게임 (Java)
[Gold II] 확장 게임 - 16920
성능 요약
메모리: 57644 KB, 시간: 492 ms
분류
너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현
제출 일자
2025년 5월 27일 23:54:02
문제 설명
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.
게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.
각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.
모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.
입력
첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S1, S2, ...SP가 주어진다.
다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.
모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.
출력
플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.
문제 풀이
bfs문제로, 조금의 복잡함이 있지만 쭉 구현하면 풀 수 있다. 플레이어별 queue를 유지하는것으로 진행했다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M, P;
static int[] S, res;
static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
static char[][] board;
static Queue<int[]>[] players;
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_16920_확장게임/input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
board = new char[N][M];
S = new int[P+1];
res = new int[P+1];
players = new ArrayDeque[P+1];
for(int i = 0; i < P+1; i++) {
players[i] = new ArrayDeque<>();
}
st = new StringTokenizer(br.readLine());
for(int i=1; i<=P; i++){
S[i] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
for(int i=0; i<N; i++){
String line = br.readLine();
for(int j=0; j<M; j++){
board[i][j] = line.charAt(j);
if(board[i][j] != '.' && board[i][j] != '#'){
int pNum = board[i][j] - '0';
players[pNum].add(new int[]{i, j});
res[pNum]++;
}
else cnt++;
}
}
int pIdx = 1;
int fail = 0;
while(cnt>0 && fail < P){
Queue<int[]> currQ = players[pIdx];
boolean flag = false;
for(int i=0; i<S[pIdx]; i++){
int size = currQ.size();
if(size == 0) break;
for(int j=0; j<size; j++){
int[] currCell = currQ.poll();
for(int k=0; k<4; k++){
int nr = currCell[0] + dr[k];
int nc = currCell[1] + dc[k];
if(isValid(nr, nc) && board[nr][nc] == '.'){
board[nr][nc] = (char)(pIdx + '0');
res[pIdx]++;
currQ.add(new int[]{nr, nc});
cnt--;
flag = true;
}
}
}
}
if(!flag) fail++;
else fail = 0;
pIdx = nextP(pIdx);
}
for(int i=1; i<=P; i++){
sb.append(res[i]).append(" ");
}
System.out.println(sb.toString());
bw.flush();
bw.close();
br.close();
}
private boolean isValid(int r, int c){
return r >= 0 && r < N && c >= 0 && c < M;
}
private int nextP(int pIdx){
return pIdx % P + 1;
}
}