https://www.acmicpc.net/problem/20056
해결 방법
빡구현..
1. 구현 방법 떠올리는게 어렵고
2. 시뮬레이션 너무 헷갈린다
생각해보면 파이어볼 이동과 합치기 밖에 없는데 머리로는 되는게 코드로는 안된다
- 파이어볼을 구조체
Fire로 관리한다.pair<int,int> p: 파이어볼의 위치m: 파이어볼의 질량s: 파이어볼의 속도d: 파이어볼의 방향cnt: 파이어볼 보드에서, 한 칸에 존재하는 파이어블의 개수를 셀 때 이용한다.
파이어볼 보드에서 이용할 것이므로, 그냥 파이어볼의 cnt는 0으로 둔다.
- 파이어볼 보드
Fire board[][]: 최대 50x50 크기이다.pair<int,int> p=={i,j}m: 해당 칸에 존재하는 파이어볼 질량의 합s: 속도의 합d: 현재 놓인 파이어볼들의 방향이 홀수로 일치 / 짝수로 일치 / 불일치 하는지 담고 있다.- 방향이 홀수로 일치 :
d = -2 - 방향이 짝수로 일치 :
d = -3 - 방향이 일치하지 않음 :
d = -1
- 방향이 홀수로 일치 :
cnt: Fire 구조체에서 설명했듯, 현재 보드 해당 칸에 존재하는 파이어볼의 개수이다.
다음과 같은 경우에 이용한다.- 보드가 비어있는지 확인
- 파이어볼을 나눌 때, 속도(속도의 합 / 파이어볼 개수)구하는 데 이용
파이어볼 이동
balls 벡터에 담겨있는 파이어볼을 하나씩 순회하며 이동시킨다.
문제 또 제대로 안읽고 벽에 부딪히면 가만히 있어야 하는 줄 알았다.
1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
그럼 그렇지..
- 다음 위치 = 현재 위치 + (이동 방향 * 속도)
- 만약
다음 위치 < 0이라면, 다음위치 += N - 만약
다음 위치 >= N이라면, 다음 위치 -= N
런타임에러 (OutOfBounds)
ㅋㅋ 이럴수가
위 방법을 다시 생각해보니, 속도가 1000으로 주어진다면 OutOfBounds는 당연하다
이동 방법 수정
- 다음 위치를 현재 위치로 초기화시킨다.
- 다음 위치 += 이동방향
속도만큼, 파이어볼을 해당 방향으로 한번씩 전진시킨다
이 과정에서 벽에 닿는다면, 처음 구현했던 것처럼 N을 더하거나 빼주며 반대편으로 이동시켜준다.
보드게임에서 말을 한번에 이동하지 않고, 한칸씩 이동시키는 것처럼, 방법을 바꾸었다
파이어볼 합치기
제출 코드는 put_board로 구현이 되어있지만,
원래는 put_board와 divide가 따로 나누어져 있었다
put_board: balls에 있는 파이어볼을 하나씩 꺼내서 보드에 내려놓는다.- 보드에 아무것도 없다면 (
board[i][j].cnt == 0), 그냥 내려놓고 cnt++ - 보드에 공이 있는 상태라면,
- 질량 추가 , 속도 추가 , cnt++
- 방향 살피기
- 해당 칸에 공이 하나밖에 없었음 : 해당 공과 방향 비교 후
짝수로 같으면 -2 / 홀수로 같으면 -3 / 다르면 -1 - 해당 칸에 있는 공들의 방향이 다름 (
board[i][j].d == -1) : 지나감 - 해당 칸에 있는 공들의 방향이 짝수로 같고, 현재 파이어볼의 방향도 짝수라면 : 지나감
- 해당 칸에 있는 공들의 방향이 홀수로 같고, 현재 파이어볼의 방향도 홀수라면 : 지나감
- 해당 칸에 있는 공들의 방향과 내 방향이 다름 :
board[i][j].d = -1
- 해당 칸에 공이 하나밖에 없었음 : 해당 공과 방향 비교 후
- 보드에 아무것도 없다면 (
put_board 동작이 끝나고 나면, balls의 파이어볼을 모두 꺼내어보았기 때문에 balls 초기화
그리고 divide에서 board를 살피며 파이어볼을 다시 balls에 담아준다.
divide: board를 하나씩 살펴본다.- 해당 칸에 아무것도 없다면 (
board[i][j].cnt == 0), 그냥 지나가기 - 해당 칸에 공이 하나만 있으면, balls에 그대로 담아줌
- 해당 칸에 공이 여러개 있는 경우,
- 질량을 5로 나눠주고, 질량이 0이라면 공을 없애야 하므로 넘어가기(continue)
- 속도는 해당 칸의 공 개수로 나눠주기
- 파이어볼의 방향이 홀/ 짝 통일이 아니라면 (
board[i][j].d == -1)
방향을 1,3,5,7로 나누어 파이어볼 4개 담아줌 - 파이어볼 방향이 홀 or 짝으로 통일이라면 방향을 0,2,4,6 으로 담아줌
근데 난 여기서 0,2,4,8로 담아버리는 실수를 했었다 ^^,,
역시 0246보다 익숙한 0248
- 해당 칸에 아무것도 없다면 (
틀렸습니다
엥 ? 왜요 ?
https://www.acmicpc.net/board/view/66407
해당 이유는 아니었지만, 해당 테케로 오류를 발견했다.
공 이동 방향은 0부터..
void put_board() {
for (int i = 0; i < balls.size(); i++) {
:
(중략)
:
if (dir > 0) { /*실수한 부분*/
if ((balls[i].d & 1) && (dir & 1)) board[pos.x][pos.y].d = -3; //홀으로 일치
else if(!(balls[i].d & 1) && !(dir & 1)) board[pos.x][pos.y].d = -2; //짝으로 일치
else board[pos.x][pos.y].d = -1; //불일치
}
:
(후략)공의 방향이 모두 짝수로 들어갔는데, 왜 대각선으로 이동할까 .. 하고 디버깅해봤더니
세상에나 .. 방향이 0일때 문제였던 것
공의 방향은 0부터인데, dir>0로 제외해버려서 방향이 0인 파이어볼이 길을 잃었다
dir>=0으로 수정하고 해결 :(
킹받네
소스 코드
#include <iostream>
#include <vector>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second
int N, M, K;
const int dx[] = { -1,-1,0,1,1,1,0,-1 };
const int dy[] = { 0,1,1,1,0,-1,-1,-1 };
struct Fire {
pii p;
int m;
int s;
int d;
int cnt = 0;
};
vector<Fire> balls;
Fire board[51][51];
bool in_board(int i, int j) {
return (0 <= i && i < N && 0 <= j && j < N);
}
void print_status() {
for (int i = 0; i < balls.size(); i++) {
cout << "#" << i<<" ("<<balls[i].p.x<<", "<<balls[i].p.y << ") : " << balls[i].m << " " << balls[i].s << " " << balls[i].d << "\n";
}
//if (balls.size()) return;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!board[i][j].m) cout << ".\t";
else cout << board[i][j].m<<"("<<board[i][j].cnt<<")" << "\t";
}
cout << "\n";
}
cout << "\n";
}
void divide() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j].cnt == 0) continue;
if (board[i][j].cnt == 1) {
balls.push_back(board[i][j]);
continue;
}
//볼 나누기
int M = board[i][j].m / 5;
if (M == 0) continue;
int S = board[i][j].s / board[i][j].cnt;
Fire f1, f2, f3, f4;
if (board[i][j].d == -1) {
f1 = { {i,j},M,S,1 };
f2 = { {i,j},M,S,3 };
f3 = { {i,j},M,S,5 };
f4 = { {i,j},M,S,7 };
}
else {
f1 = { {i,j},M,S,0 };
f2 = { {i,j},M,S,2 };
f3 = { {i,j},M,S,4 };
f4 = { {i,j},M,S,6 };
}
balls.push_back(f1); balls.push_back(f2); balls.push_back(f3); balls.push_back(f4);
}
}
}
void put_board() {
for (int i = 0; i < balls.size(); i++) {
pii pos = balls[i].p;
if (board[pos.x][pos.y].cnt == 0) {
board[pos.x][pos.y] = balls[i];
board[pos.x][pos.y].cnt = 1;
}
else {
board[pos.x][pos.y].m += balls[i].m;
board[pos.x][pos.y].s += balls[i].s;
board[pos.x][pos.y].cnt++;
int dir = board[pos.x][pos.y].d;
if (dir >= 0) {
if ((balls[i].d & 1) && (dir & 1)) board[pos.x][pos.y].d = -3; //홀으로 일치
else if(!(balls[i].d & 1) && !(dir & 1)) board[pos.x][pos.y].d = -2; //짝으로 일치
else board[pos.x][pos.y].d = -1; //불일치
}
else {
if (dir == -1) continue;
if (dir == -2 && !(balls[i].d & 1)) continue;
if (dir == -3 && (balls[i].d & 1)) continue;
board[pos.x][pos.y].d = -1;
}
}
}
balls.clear();
divide();
}
void move() {
for (int i = 0; i < balls.size(); i++) {
int nx = balls[i].p.x;
int ny = balls[i].p.y;
for (int j = balls[i].s; j > 0; j--) {
nx += dx[balls[i].d];
ny += dy[balls[i].d];
if (nx < 0) nx += N; if (nx >= N) nx -= N;
if (ny < 0) ny += N; if (ny >= N) ny -= N;
}
balls[i].p = { nx,ny };
balls[i].cnt = 0;
}
}
void clean_board() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Fire newball = { {0,0},0,0,0,0 };
board[i][j] = newball;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
int X, Y, M, S, D; cin >> X >> Y >> M >> S >> D;
balls.push_back({{X-1,Y-1},M,S,D});
}
while (K--) {
//cout << "* " << K << " ";
move();
//cout << "after move \n"; print_status();
put_board();
//cout << "after put and divide\n"; print_status();
clean_board();
}
int ans = 0;
for (int i = 0; i < balls.size(); i++) {
ans += balls[i].m;
}
cout << ans;
}제출 결과
HIU. CE / LG Elec.