1. 문제
설명
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.
게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.
각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.
모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.
입력
첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S1, S2, ...SP가 주어진다.
다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.
모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.
출력
플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.
2. 풀이
어느정도 구현력을 요구하는 문제입니다.
하지만 차근차근 하나씩 구현하면 못풀 것도 없는 문제입니다.
계획1 - 플레이어의 각자 성의 좌표를 담는 큐 배열을 선언합니다.
#define PLAYER_COUNT 9
queue<pair<int, int>> players[PLAYER_COUNT];제가 늘 중요하게 생각하고 강조하는 부분은
'어떻게 현실 세계의 복잡한 문제를 컴퓨터가 이해할 수 있게 단순화 할 것인가?' 입니다.
이 때 어떤 자료구조를 쓰느냐에 따라 난이도는 천차만별입니다.
저는 플레이어들이 각각 성의 좌표를 담는 큐를 가지고 있고,
그 안에 들어있는 좌표를 이용해서 확장해나가면 된다고 생각했습니다.
계획2 - 각각의 플레이어큐에 성의 좌표를 넣습니다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
if (isChar(board[i][j])) continue;
int playerNum = board[i][j] - '0' - 1;
players[playerNum].push({ i, j }); // 각각의 플레이어큐에 성의 좌표를 넣습니다.
board[i][j] = '0' + playerNum;
}
}계획1에서 선언한 플레이어큐 배열에 각 플레이어가 가지고 있는 성의 좌표를 넣습니다.
이 때, 각 플레이어들의 점수를 합산하기 좋도록 숫자 0에 맞춰줬습니다. ex) 1 -> 0, 2 -> 1
계획3 - 1번부터 P번 플레이어들을 차례대로 확장시킵니다.
for (int i = 0; i < P; i++) {
// 각 플레이어는 s[i]번 만큼 확장 가능
for (int step = 0; step < S[i]; step++) {
int size = players[i].size();
// 더 이상 확장할 수 없을 때
if (!size) break;
// 현재 가지고 있는 좌표의 개수만큼 진행
for (int j = 0; j < size; j++) {
int y = players[i].front().first;
int x = players[i].front().second;
players[i].pop();
// 4방향 탐색
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (board[ny][nx] != '.') continue;
players[i].push({ ny, nx }); // 확장한 지점의 좌표 삽입
board[ny][nx] = '0' + i; // 영역 표시
isContinue = 1;
}
}
}
}이 부분이 조금 까다로웠는데요. 성은 확장할 때, 회전하면서 확장이 가능합니다.
만약 확장 가능한 횟수가 3번일 때, → → →뿐만 아니라 → ↑ ← 이런 식으로 확장이 가능합니다.
그래서 현재 보고있는 좌표에 대해서 매번 4방향 탐색을 해줘야하고,
이 행동을 S[i]번 반복하면 됩니다.
3. 전체 코드
#define PLAYER_COUNT 9
#define MAX 1000
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int N, M, P;
int S[PLAYER_COUNT]; // 한 턴에 각 플레이어들이 확장할 수 있는 횟수
int scores[PLAYER_COUNT]; // 점수 합산 배열
char board[MAX][MAX]; // 게임판
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
queue<pair<int, int>> players[PLAYER_COUNT]; // 계획1 - 플레이어의 각자 성의 좌표를 담는 큐 배열을 선언합니다.
bool isChar(char ch) {
return ch == '#' || ch == '.';
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> P;
for (int i = 0; i < P; i++) cin >> S[i];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
if (isChar(board[i][j])) continue;
int playerNum = board[i][j] - '0' - 1;
players[playerNum].push({ i, j }); // 계획2 - 각각의 플레이어큐에 성의 좌표를 넣습니다.
board[i][j] = '0' + playerNum;
}
}
while (1) {
int isContinue = 0;
// 계획3 - 1번부터 P번 플레이어들을 차례대로 확장시킵니다.
for (int i = 0; i < P; i++) {
// 각 플레이어는 s[i]번 만큼 확장 가능
for (int step = 0; step < S[i]; step++) {
int size = players[i].size();
// 더 이상 확장할 수 없을 때
if (!size) break;
// 현재 가지고 있는 좌표의 개수만큼 진행
for (int j = 0; j < size; j++) {
int y = players[i].front().first;
int x = players[i].front().second;
players[i].pop();
// 4방향 탐색
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (board[ny][nx] != '.') continue;
players[i].push({ ny, nx }); // 확장한 지점의 좌표 삽입
board[ny][nx] = '0' + i; // 영역 표시
isContinue = 1;
}
}
}
}
// 단 한 플레이어도 확장하지 못했을 때 loop out
if (!isContinue) break;
}
// 계획3 - 점수를 합산합니다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (isChar(board[i][j])) continue;
scores[board[i][j] - '0']++;
}
}
for (int i = 0; i < P; i++) cout << scores[i] << " ";
return 0;
}