문제 링크 : https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
문제 요약
1. N,M,K가 입력된다. ( 4<=N<=50, 0<=M<=N2, 1<=K<=1,000)
2. 보드판 N*N이 생성된다. 이 보드판은 1~N번까지 번호가 매겨져있으며, 1번 행은 N번과 연결되고 1번 열은 N번가 연결되어있다.
3. M개의 파이어볼 정보가 주어진다. 파이어볼은 r, c, m, s, d의 정보가 주어지며, 각각 행,열,질량,속도,방향이다.
4. 모든 파이어볼이 자신의 방향 d로 속도 s만큼 이동한다.
5. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
(1) 같은 칸에 있던 파이어볼이 모두 합쳐진다.
(2) 그리고 4개로 나누어진다.
(3) 나누어지는 파이어볼의 질량, 속도, 방향은 다음과 같다.
- 질량 = 합쳐진 파이어볼 질량 / 5
- 속도 = 합쳐진 파이어볼 속도 / 합쳐진 파이어볼 갯수
- 방향 = 합쳐진 파이어볼의 방향이 모두 홀수거나 짝수일 경우 0,2,4,6이 되고, 그렇지 않을 경우 1,3,5,7이 된다.
- 만약 질량이 0이라면 파이어볼은 사라진다.
6. 마법사 상어가 이동을 K번 명령한 뒤, 남아있는 파이어볼 질량의 합을 구해보자.
핵심 포인트
구현 문제인만큼 놓칠 수 있는 부분들을 하나하나 잘 살펴봐야합니다.
예컨데 이 문제에서 놓치기 쉬운 주의사항은 다음과 같습니다.
- 배열의 1번과 N번은 연결되어있습니다. 즉, N번에서 +1을 이동하면 1번으로 돌아오게 됩니다.
- 만약 1,1의 위치에서 방향 (-1,0) * 속도 50의 위치로 가게되는 경우처럼, 마이너스에 대한 방향 처리를 주의해야합니다.
- 2개 이상의 파이어볼이 있는 칸에서는 위의 조건에 따라 4개로 나누어져야 하지만, 파이어볼이 1개만 있을 경우 그 자리에 그대로 남아있게 됩니다.
문제 풀이
1. 전역함수와 input함수 입니다. input 함수를 별도로 구현하여 보다 쉽게 이해할 수 있도록 만들었습니다.
int N,M,K;
pair<int,int> blow[] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
struct fire{
int r; // 행
int c; // 열
int m; // 질량
int s; // 속도
int d; // 방향
};
struct done{
int m; // 질량
int s; // 속도
int d; // 방향
};
queue<fire> q;
vector<done> vc[51][51];
void input(){
cin >> N >> M >> K;
for(int i=0; i<M; i++){
int r=0,c=0,m=0,s=0,d=0;
cin >> r >> c >> m >> s >> d;
q.push({r,c,m,s,d});
}
}이동하기 전의 파이어볼은 q에 큐 형식으로 저장하며, 이동을 완료한 파이어볼은 vc벡터에 저장합니다.
2. 다음은 파이어볼의 이동 위치를 구하는 함수입니다.
void move(){
while(!q.empty()){
fire f = q.front();
q.pop();
int y = f.r;
int x = f.c;
int mm = f.m;
int ss = f.s;
int dd = f.d; // 행, 열
y += (blow[dd].first * ss); // 1
x += (blow[dd].second * ss); // 2
if(y<0) y=(N-abs(y%N))%N; // 3
else y%=N;
if(x<0) x=(N-abs(x%N))%N; // 4
else x%=N;
if(y==0) y=N; if(x==0) x=N; // 5
vc[y][x].push_back({mm,ss,dd}); // 6
}
}위 코드에서 파이어볼의 위치, 특히 음수가 나오는 경우의 위치를 잘 이해해야합니다.
(1) 방향 * 속도의 y값을 y변수에 더해줍니다.
(2) 방향 * 속도의 x값을 x변수에 더해줍니다.
(3) 만약 y값이 음수라면, 이를 다시 양수로 저장해줍니다. 위의 공식이 이해가 안될경우 직접 예시를 작성하시면 보다 쉽게 이해할 수 있습니다. 만약 y값이 양수라면 %N만 해주면 됩니다.
(4) x역시 (3)번과 동일하게 진행합니다.
(5) 만약 x와 y의 결과가 0일 경우, 이는 N번에 위치함을 뜻합니다. 각 값을 N으로 다시 저장합니다.
(6) 이동한 자리에 파이어볼의 질량, 속도, 방향을 저장합니다.
3. 다음은 파이어볼을 분리하는 함수입니다.
void shoot(){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(vc[i][j].size()==1){ // 1
q.push({i,j,vc[i][j].front().m,vc[i][j].front().s,vc[i][j].front().d});
vc[i][j].clear();
}
else if(vc[i][j].size()>=2){ // 2
int nn = vc[i][j].size(); // 3
int mm = 0;
int ss = 0;
int dd = -1; // -2면 홀수로 간다
for(int x=0; x<vc[i][j].size(); x++){ // 4
mm += vc[i][j][x].m;
ss += vc[i][j][x].s;
if(dd==-1) dd = vc[i][j][x].d; // 5
else if(dd>=0){
if(dd%2!=vc[i][j][x].d%2) dd=-2;
}
}
vc[i][j].clear(); // 6
if(mm/5<=0) continue; // 7
if(dd>=0){ // 8
for(int x=0; x<8; x+=2) q.push({i,j,mm/5,ss/nn,x});
}else{ // 9
for(int x=1; x<8; x+=2) q.push({i,j,mm/5,ss/nn,x});
}
}
}
}
}(1) 만약 vc[i][j]의 사이즈가 1이라면, 파이어볼이 1개 있다는 뜻입니다. 해당 파이어볼을 그대로 q에 저장합니다.
저장을 한 뒤 vc[i][j]를 clear()해주어 벡터를 비어주는 과정을 잊으면 안됩니다.
(2) 만약 vc[i][j]의 사이즈가 2이상이라면, 파이어볼이 4개로 쏘아질 수 있는지 확인을 해봐야 합니다.
(3) nn은 vc[i][j]의 사이즈, mm은 vc[i][j]에 위치한 파이어볼의 총 질량, ss는 속도의 총 합, dd는 어느 방향으로 쪼개질지 구하는 변수입니다.
(4) vc[i][j]의 사이즈만큼 for문을 돌려 mm,ss의 합을 구해줍니다.
(5) 속도의 경우, 만약 dd의 값이 -1인 상태라면 최초의 파이어볼의 값을 받는 경우입니다. dd의 값을 vc[i][j][x].d로 저장해줍니다.
(6) 만약 dd의 값이 0이상일 경우, 현재 파이어볼의 방향과 같은지를 판단합니다. 방향이 다를경우 dd를 -2로 저장합니다.
(6) vc[i][j] 벡터를 clear()합니다.
(7) 만약 mm/5가 0 이하일 경우, 파이어볼은 그대로 사라집니다. 때문에 continue를 합니다.
(8) 만약 dd가 0 이상일 경우, 파이어볼은 짝수방향으로 흩어집니다. 짝수방향으로 각 파이어볼들을 q에 저장합니다.
(9) 아닐 경우, 파이어볼은 홀수방향으로 흩어집니다. 홀수방향으로 각 파이어볼들을 q에 저장합니다.
4. 마지막으로 정답을 구하는 함수입니다.
int answer(){
int ans = 0;
while(!q.empty()){
int temp = q.front().m;
q.pop();
ans+=temp;
}
return ans;
}q에있는 모든 질량을 더해준 뒤 반환하면 됩니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N,M,K;
pair<int,int> blow[] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
struct fire{
int r; // 행
int c; // 열
int m; // 질량
int s; // 속도
int d; // 방향
};
struct done{
int m; // 질량
int s; // 속도
int d; // 방향, -1로 초기화
};
queue<fire> q;
vector<done> vc[51][51];
void input(){
cin >> N >> M >> K;
for(int i=0; i<M; i++){
int r=0,c=0,m=0,s=0,d=0;
cin >> r >> c >> m >> s >> d;
q.push({r,c,m,s,d});
}
}
void move(){
while(!q.empty()){
fire f = q.front();
q.pop();
int y = f.r;
int x = f.c;
int mm = f.m;
int ss = f.s;
int dd = f.d; // 행, 열
y += (blow[dd].first * ss);
x += (blow[dd].second * ss);
if(y<0) y=(N-abs(y%N))%N;
else y%=N;
if(x<0) x=(N-abs(x%N))%N;
else x%=N;
if(y==0) y=N; if(x==0) x=N;
vc[y][x].push_back({mm,ss,dd});
}
}
void shoot(){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(vc[i][j].size()==1){
q.push({i,j,vc[i][j].front().m,vc[i][j].front().s,vc[i][j].front().d});
vc[i][j].clear();
}
else if(vc[i][j].size()>=2){
int nn = vc[i][j].size();
int mm = 0;
int ss = 0;
int dd = -1; // -2면 홀수로 간다
for(int x=0; x<vc[i][j].size(); x++){
mm += vc[i][j][x].m;
ss += vc[i][j][x].s;
if(dd==-1) dd = vc[i][j][x].d;
else if(dd>=0){
if(dd%2!=vc[i][j][x].d%2) dd=-2;
}
}
vc[i][j].clear();
if(mm/5<=0) continue;
if(dd>=0){
for(int x=0; x<8; x+=2) q.push({i,j,mm/5,ss/nn,x});
}else{
for(int x=1; x<8; x+=2) q.push({i,j,mm/5,ss/nn,x});
}
}
}
}
}
int answer(){
int ans = 0;
while(!q.empty()){
int temp = q.front().m;
q.pop();
ans+=temp;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
while(K--){
move();
shoot();
}
cout << answer() << "\n";
return 0;
}
'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
| 백준 14938번 서강그라운드 (C++) (0) | 2021.09.02 |
|---|---|
| 프로그래머스 직업군 추천하기 (C++) (0) | 2021.08.31 |
| 백준 19583번 싸이버개강총회 (C++) (0) | 2021.08.25 |
| 백준 4485번 녹색 옷 입은 애가 젤다지? (C++) (0) | 2021.08.22 |
| 백준 1253번 좋다 (C++) (0) | 2021.08.19 |