💻 현생/⛓ 알고리즘
[백준] 20056번 : 마법사 상어와 파이어볼
영이오
2021. 8. 31. 15:07
문제
풀이
메모리면에서 그닥 효율적인 코드는 아닌 것 같지만 적어본다.
할 일은 2개밖에 없다
1. 파이어볼 이동
2. 파이어볼 분리
파이어볼의 상태를 저장할 구조체가 필요하겠고, 한 좌표에 둘 이상의 파이어볼이 있는지도 잘 체크해야 하고...
또 사라진 파이어볼을 어떻게 처리할지도 생각해야 한다.
아 그리고 격자의 크기가 최대 50인데 속력의 크기는 최대 1,000이다. 이걸 하나하나 움직이는건 당연히 비효율적이니 모듈러 연산을 사용해야 한다.
소스코드
#include <iostream>
#include <vector>
using namespace std;
struct info {
bool is_remain;
int r, c, m, s, d;
};
int N;
vector<vector<vector<int>>> board;
vector<info> fire;
pair<int, int> dir[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
void moveFire(int idx) { //파이어볼 이동
info cur = fire[idx];
//한번에 이동
int row = (cur.r + (cur.s * dir[cur.d].first)) % N;
int col = (cur.c + (cur.s * dir[cur.d].second)) % N;
//음수 처리
if (row < 0)
row += N;
if (col < 0)
col += N;
board[row][col].push_back(idx); //board에 표시
fire[idx].r = row;
fire[idx].c = col;
}
void splitFire(int row, int col) { //파이어볼 분리
vector<int> fires = board[row][col];
int mass = 0, speed = 0, odd_cnt = 0, even_cnt = 0, size = fires.size();
for (int i = 0; i < size; i++) {
info &cur = fire[fires[i]];
cur.is_remain = false; //기존 파이어볼 삭제
mass += cur.m; //총 질량
speed += cur.s; //총 속력
(cur.d % 2 == 0) ? even_cnt++ : odd_cnt++; //방향 홀짝 체크
}
if (mass / 5 == 0) //질량이 0인지 확인
return;
int init = 1; //합쳐지는 파이어볼의 방향
if (odd_cnt == 0 || even_cnt == 0) //전부 홀수 or 짝수라면 0부터 시작
init = 0;
for (int i = 0; i < 4; i++) { //새로운 파이어볼 추가
fire.push_back({true, row, col, mass / 5, speed / size, init});
init += 2;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int M, K;
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
int r, c, m, s, d;
cin >> r >> c >> m >> s >> d;
fire.push_back({true, r - 1, c - 1, m, s, d});
}
while (K--) {
board.assign(N, vector<vector<int>>(N, vector<int>(0))); //board 초기화
for (int i = 0; i < fire.size(); i++) {
if (fire[i].is_remain) //활성화된 파이어볼이라면 이동
moveFire(i);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j].size() > 1) //파이어볼이 둘 이상 있다면
splitFire(i, j);
}
}
}
int result = 0;
for (int i = 0; i < fire.size(); i++) {
if (fire[i].is_remain) //남아있는 파이어볼만 질량 계산
result += fire[i].m;
}
cout << result;
}전체 소스코드다.
struct info {
bool is_remain;
int r, c, m, s, d;
};
int N;
vector<vector<vector<int>>> board;
vector<info> fire;
pair<int, int> dir[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};파이어볼의 상태를 저장할 구조체와 격자, 파이어볼 벡터, 그리고 방향 계산에 쓸 pair 배열도 만든다.
구조체에서 is_remain은 이 파이어볼이 여전히 격자에 존재하는지를 저장하는 bool 변수다.
ios::sync_with_stdio(false);
cin.tie(NULL);
int M, K;
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
int r, c, m, s, d;
cin >> r >> c >> m >> s >> d;
fire.push_back({true, r - 1, c - 1, m, s, d});
}입력 받고
while (K--) {
board.assign(N, vector<vector<int>>(N, vector<int>(0))); //board 초기화
for (int i = 0; i < fire.size(); i++) {
if (fire[i].is_remain) //활성화된 파이어볼이라면 이동
moveFire(i);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j].size() > 1) //파이어볼이 둘 이상 있다면
splitFire(i, j);
}
}
}K번의 while문을 돈다.
board.assign(N, vector<vector<int>>(N, vector<int>(0))); //board 초기화먼저 격자의 상태는 매 루프마다 초기화 한다...기존 파이어볼을 삭제하고 이동하느니 초기화하는게 나을 것 같았다.
for (int i = 0; i < fire.size(); i++) {
if (fire[i].is_remain) //활성화된 파이어볼이라면 이동
moveFire(i);
}모든 파이어볼에 대해 is_remain이 true라면 moveFire 함수를 호출해서 파이어볼을 이동한다.
void moveFire(int idx) { //파이어볼 이동
info cur = fire[idx];
//한번에 이동
int row = (cur.r + (cur.s * dir[cur.d].first)) % N;
int col = (cur.c + (cur.s * dir[cur.d].second)) % N;
//음수 처리
if (row < 0)
row += N;
if (col < 0)
col += N;
board[row][col].push_back(idx); //board에 표시
fire[idx].r = row;
fire[idx].c = col;
}moveFire 함수는 간단하다.
//한번에 이동
int row = (cur.r + (cur.s * dir[cur.d].first)) % N;
int col = (cur.c + (cur.s * dir[cur.d].second)) % N;먼저 모듈러 연산으로 파이어볼의 새로운 좌표를 찾는다.
//음수 처리
if (row < 0)
row += N;
if (col < 0)
col += N;그 결과가 음수일 수도 있으니 그것도 고려한다.
board[row][col].push_back(idx); //board에 표시
fire[idx].r = row;
fire[idx].c = col;파이어볼의 새로운 위치를 격자에 표시하고 fire 자체도 r, c 값을 갱신한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j].size() > 1) //파이어볼이 둘 이상 있다면
splitFire(i, j);
}
}다시 메인으로 돌아와서 board를 돌다가 둘 이상의 파이어볼이 있다면 해당 좌표에 대해 splitFire 함수를 호출한다.
void splitFire(int row, int col) { //파이어볼 분리
vector<int> fires = board[row][col];
int mass = 0, speed = 0, odd_cnt = 0, even_cnt = 0, size = fires.size();
for (int i = 0; i < size; i++) {
info &cur = fire[fires[i]];
cur.is_remain = false; //기존 파이어볼 삭제
mass += cur.m; //총 질량
speed += cur.s; //총 속력
(cur.d % 2 == 0) ? even_cnt++ : odd_cnt++; //방향 홀짝 체크
}
if (mass / 5 == 0) //질량이 0인지 확인
return;
int init = 1; //합쳐지는 파이어볼의 방향
if (odd_cnt == 0 || even_cnt == 0) //전부 홀수 or 짝수라면 0부터 시작
init = 0;
for (int i = 0; i < 4; i++) { //새로운 파이어볼 추가
fire.push_back({true, row, col, mass / 5, speed / size, init});
init += 2;
}
}이것도 엄청 어렵진 않다
for (int i = 0; i < size; i++) {
info &cur = fire[fires[i]];
cur.is_remain = false; //기존 파이어볼 삭제
mass += cur.m; //총 질량
speed += cur.s; //총 속력
(cur.d % 2 == 0) ? even_cnt++ : odd_cnt++; //방향 홀짝 체크
}먼저 해당 좌표의 모든 파이어볼에 대해 is_remain을 false로 바꿔준다. 합쳐져서 사라질 것이기 때문이다.
총 질량과 총 속력을 갱신하고 방향의 홀짝을 판단한다.
if (mass / 5 == 0) //질량이 0인지 확인
return;그렇게 구한 총 질량을 5로 나눈 값이 0이라면 없는 파이어볼이니 그냥 리턴한다.
int init = 1; //합쳐지는 파이어볼의 방향
if (odd_cnt == 0 || even_cnt == 0) //전부 홀수 or 짝수라면 0부터 시작
init = 0;새로운 파이어볼의 방향을 0부터 시작할지 1부터 시작할지도 정하고...
for (int i = 0; i < 4; i++) { //새로운 파이어볼 추가
fire.push_back({true, row, col, mass / 5, speed / size, init});
init += 2;
}그리곤 그냥 새로운 파이어볼을 파이어 벡터에 추가하면 된다.
int result = 0;
for (int i = 0; i < fire.size(); i++) {
if (fire[i].is_remain) //남아있는 파이어볼만 질량 계산
result += fire[i].m;
}
cout << result;반복문을 다 돌면 남아있는 파이어볼들에 대해서만 질량을 전부 더해서 출력한다.