728x90
반응형
https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ20056
//
// Created by 최화연 on 2022/04/13.
//
#include <iostream>
#include <vector>
using namespace std;
int N, M, K;
struct Fireball {
int r;
int c;
int m;
int s;
int d;
};
Fireball fireball;
vector<Fireball> fireballs;
vector<Fireball> board[50][50];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
void move_fireballs() {
for(int i=0; i<K; i++) {
//초기화
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
board[r][c].clear();
}
}
//1.
for (int j=0; j<fireballs.size(); j++) {
int nr = fireballs[j].r + dy[fireballs[j].d] * (fireballs[j].s % N);
int nc = fireballs[j].c + dx[fireballs[j].d] * (fireballs[j].s % N);
if (nr < 0) nr += N;
if (nr >= N) nr -= N;
if (nc < 0) nc += N;
if (nc >= N) nc -= N;
fireballs[j].r = nr;
fireballs[j].c = nc;
board[nr][nc].push_back(fireballs[j]);
}
//2.
fireballs.clear();
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
if (board[r][c].size() == 1) {
fireballs.push_back(board[r][c].front());
}
else if (board[r][c].size() >= 2) {
int sum_m = 0;
int sum_s = 0;
bool check_d = true;
int d = board[r][c].front().d % 2;
for (int j=0; j<board[r][c].size(); j++) {
sum_m += board[r][c][j].m;
sum_s += board[r][c][j].s;
if (board[r][c][j].d % 2 != d) check_d = false;
}
int m = sum_m/5;
int s = sum_s/board[r][c].size();
if (m == 0) continue;
if (check_d) {
for (int d=0; d<=6; d+=2) {
fireballs.push_back({r, c, m, s, d});
}
}
else {
for (int d=1; d<=7; d+=2) {
fireballs.push_back({r, c, m, s, d});
}
}
}
}
}
}
}
int get_fireballs_m_sum() {
int sum = 0;
for(int i=0; i<fireballs.size(); i++) {
sum += fireballs[i].m;
}
return sum;
}
int main(int argc, const char * argv[]) {
cin >> N >> M >> K;
for (int i=0; i<M; i++) {
cin >> fireball.r >> fireball.c >> fireball.m >> fireball.s >> fireball.d;
fireball.r--;
fireball.c--;
fireballs.push_back(fireball);
}
move_fireballs();
cout << get_fireballs_m_sum() << endl;
return 0;
}풀이 과정
#include <iostream>
#include <vector>
using namespace std;
int N, M, K;
struct Fireball {
int r;
int c;
int m;
int s;
int d;
};
Fireball fireball;
vector<Fireball> fireballs;
vector<Fireball> board[50][50];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
void move_fireballs() {
for(int i=0; i<K; i++) {
//초기화
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
board[r][c].clear();
}
}
//1.
for (int j=0; j<fireballs.size(); j++) {
int nr = fireballs[j].r + dy[fireballs[j].d] * (fireballs[j].s % N);
int nc = fireballs[j].c + dx[fireballs[j].d] * (fireballs[j].s % N);
if (nr < 0) nr += N;
if (nr >= N) nr -= N;
if (nc < 0) nc += N;
if (nc >= N) nc -= N;
fireballs[j].r = nr;
fireballs[j].c = nc;
board[nr][nc].push_back(fireballs[j]);
}
//2.
fireballs.clear();
for(int r=0; r<N; r++) {
for(int c=0; c<N; c++) {
if (board[r][c].size() == 1) {
fireballs.push_back(board[r][c].front());
}
else if (board[r][c].size() >= 2) {
int sum_m = 0;
int sum_s = 0;
bool check_d = true;
int d = board[r][c].front().d % 2;
for (int j=0; j<board[r][c].size(); j++) {
sum_m += board[r][c][j].m;
sum_s += board[r][c][j].s;
if (board[r][c][j].d % 2 != d) check_d = false;
}
int m = sum_m/5;
int s = sum_s/board[r][c].size();
if (m == 0) continue;
if (check_d) {
for (int d=0; d<=6; d+=2) {
fireballs.push_back({r, c, m, s, d});
}
}
else {
for (int d=1; d<=7; d+=2) {
fireballs.push_back({r, c, m, s, d});
}
}
}
}
}
}
}
int get_fireballs_m_sum() {
int sum = 0;
for(int i=0; i<fireballs.size(); i++) {
sum += fireballs[i].m;
}
return sum;
}
int main(int argc, const char * argv[]) {
cin >> N >> M >> K;
for (int i=0; i<M; i++) {
cin >> fireball.r >> fireball.c >> fireball.m >> fireball.s >> fireball.d;
fireball.r--;
fireball.c--;
fireballs.push_back(fireball);
}
move_fireballs();
cout << get_fireballs_m_sum() << endl;
return 0;
}이전 풀이
풀이 시간 54분
#include <iostream>
#include <queue>
using namespace std;
int N, M, K;
//1 <= r,c <= N
//board[r][c] = (r, c)에 존재하는 파이어 볼의 개수
int board[51][51] = {0, };
int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
struct Fireball{
int r;
int c;
int m;
int s;
int d;
};
Fireball fireball;
struct cmp{
bool operator()(Fireball f1, Fireball f2){
//행 번호가 같은 경우,
if(f1.r == f2.r){
//열 번호가 작은 순서대로 정렬
return f1.c > f2.c;
}
//행 번호가 작은 순대로 정렬
return f1.r > f2.r;
}
};
//파이어볼들을 담는 큐
priority_queue<Fireball, vector<Fireball>, cmp> fireballs;
//이동한 파이어볼들을 담는 큐
priority_queue<Fireball, vector<Fireball>, cmp> new_fireballs;
//같은 위치의 파이어볼들을 담을 벡터
vector<Fireball> group_fireballs;
int total_fireballs_mass = 0;
void move_fireballs(){
//K번 명령 실행
for(int k=0; k<K; k++){
total_fireballs_mass = 0;
//1. 파이어볼 움직이기
while(!fireballs.empty()){
fireball = fireballs.top();
fireballs.pop();
int new_r = fireball.r;
int new_c = fireball.c;
//d 방향으로 한 칸씩 움직이면서 총 s만큼 움직인다
for(int s=fireball.s; s>0; s--){
new_r += dr[fireball.d];
new_c += dc[fireball.d];
//1행과 N행이 연결되어 있다
//new_r이 0으로 범위를 벗어난 경우, N행으로 바꿔준다
if(new_r == 0) new_r = N;
//new_r이 N+1로 범위를 벗어난 경우, 1행으로 바꿔준다
else if(new_r == N+1) new_r = 1;
//1열과 N열이 연결되어 있다
//new_c가 0으로 범위를 벗어난 경우, N열로 바꿔준다
if(new_c == 0) new_c = N;
//new_c가 N+1으로 범위를 벗어난 경우, 1열로 바꿔준다
else if(new_c == N+1) new_c = 1;
}
//파이어볼이 이동했으므로 해당 위치의 파이어볼 개수 빼주기
board[fireball.r][fireball.c]--;
//새로운 위치로 파이어볼 이동
fireball.r = new_r;
fireball.c = new_c;
board[fireball.r][fireball.c]++;
new_fireballs.push(fireball);
}
//2. 이동한 파이어볼 처리하기
while(!new_fireballs.empty()){
fireball = new_fireballs.top();
new_fireballs.pop();
//해당 위치의 파이어볼이 1개인 경우,
if(board[fireball.r][fireball.c] == 1){
//fireballs 우선순위 큐에 담아주고 파이어볼의 총 질량 증가
fireballs.push(fireball);
total_fireballs_mass += fireball.m;
continue;
}
//해당 위치의 파이어볼이 2개 이상인 경우, group_fireballs에 파이어볼들을 추가한다
int cnt = board[fireball.r][fireball.c]-1;
group_fireballs.clear();
group_fireballs.push_back(fireball);
while(cnt > 0){
fireball = new_fireballs.top();
new_fireballs.pop();
group_fireballs.push_back(fireball);
cnt--;
}
int sum_m = 0;
int sum_s = 0;
int d = 0;
for(int i=0; i<group_fireballs.size(); i++){
sum_m += group_fireballs[i].m;
sum_s += group_fireballs[i].s;
d += (group_fireballs[i].d%2);
}
int m = sum_m/5;
//합쳐진 파이어볼의 질량이 0인 경우, 파이어볼이 소멸된다
if(m == 0){
board[group_fireballs[0].r][group_fireballs[0].c] = 0;
group_fireballs.clear();
continue;
}
//파이어볼이 소멸되지 않은 경우,
fireball.r = group_fireballs[0].r;
fireball.c = group_fireballs[0].c;
fireball.m = m;
fireball.s = sum_s/group_fireballs.size();
//4개의 파이어볼로 나뉜다
board[fireball.r][fireball.c] = 4;
total_fireballs_mass += (4*fireball.m);
//합쳐진 파이어볼의 방향이 모두 짝수이거나, 홀수인 경우
if(d == 0 || d == group_fireballs.size()){
//0, 2, 4, 6의 방향을 갖는 파이어볼로 나뉜다
for(int d=0; d<=6; d+=2){
fireball.d = d;
fireballs.push(fireball);
}
}
//합쳐진 파이어볼의 방향이 모두 짝수이거나, 홀수가 아닌 경우
else{
//1, 3, 5, 7의 방향을 갖는 파이어볼로 나뉜다
for(int d=1; d<=7; d+=2){
fireball.d = d;
fireballs.push(fireball);
}
}
}
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M >> K;
for(int i=0; i<M; i++){
cin >> fireball.r >> fireball.c >> fireball.m >> fireball.s >> fireball.d;
//파이어볼의 위치에 파이어볼 개수 카운팅
board[fireball.r][fireball.c]++;
//파이어볼을 담는 우선순위 큐에 파이어볼 추가
fireballs.push(fireball);
}
//파이어볼이 0개인 경우,
if(M == 0){
cout << 0 << endl;
return 0;
}
move_fireballs();
cout << total_fireballs_mass << endl;
return 0;
}
//시간복잡도 = O(K*2500*4*1000) = O(n), 공간복잡도 = O(M)
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 12100 2048(Easy) C++ (0) | 2021.10.17 |
|---|---|
| 백준 21611 마법사 상어와 블리자드 C++ (0) | 2021.10.15 |
| 백준 21609 상어 중학교 C++ (0) | 2021.10.14 |
| 백준 20061 모노미노도미노 2 C++ (0) | 2021.10.14 |
| 백준 12015 가장 긴 증가하는 부분 수열 2 Python 3 (0) | 2021.10.08 |