[Algorithm][C++] BOJ 20056 마법사 상어와 파이어볼

url: https://www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

 

풀이 핵심

1. STL queue 활용 문제 풀이 (한 공간에 여러 개의 파이어볼 있을 수 있음)

 

2. 이동 시킬 때 이미 이동했던 파이어볼을 또 이동시키지 않기 위해 동일한 크기의 queue temp 배열 이용

 

3. 맵을 넘어갈 때는 다음 처럼 처리

for (int i = 0; i < cur.s; i++) {
  nr += dr[cur.d], nc += dc[cur.d];
  if (nr < 1) nr = N;
  else if (nr > N) nr = 1;
  if (nc < 1) nc = N;
  else if (nc > N) nc = 1;
}

 

4. move 할 때 이동 한 것은 temp에 저장, 이동이 모두 끝나고 temp에서 2개 이상의 파이어볼이 같은 공간에 있을 때 4개로 쪼갠 뒤 map에 저장 (여기서 질량을 합친 것은 쪼개지 않는다)

이런 식으로 처리하면 move 다시 시작할 때마다 temp 또는 map을 초기화 시키기거나 복사해주는 과정이 필요하지 않다. (왜냐하면 move 할 때는 map은 모두 pop 처리되고 합치고 쪼개질 때 temp는 모두 pop 처리 되기 때문)

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue> // STL 큐를 활용해 문제 풀이
using namespace std;

int N, M, K; // 맵 크기, 초기 파이어볼 개수, 이동 횟수
struct info { int m, s, d; }; // 질량, 속도, 방향
// 방향은 북(0), 북동(1), 동(2), 남동(3), 남(4), 남서(5), 서(6), 북서(7)
const int dr[] = { -1,-1,0,1,1,1,0,-1 };
const int dc[] = { 0,1,1,1,0,-1,-1,-1 };
queue <info> map[51][51]; // 질량, 속도, 방향 정보를 담을 수 있는 큐 map 배열

// 이동하기
void move() {
	queue <info> temp[51][51]; // map과 같은 크기의 큐 배열 생성
    
    // 이동하기
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
        // 합치고 쪼개 진 뒤 한 공간에 여러개의 파이어볼이 있을 수 있음
			while (!map[r][c].empty()) {
				info cur = map[r][c].front();
				map[r][c].pop();
				int nr = r, nc = c;
                // 속도 만큼 반복
				for (int i = 0; i < cur.s; i++) {
					nr += dr[cur.d], nc += dc[cur.d];
                    // 맵의 크기를 넘어갈 때 다음과 같이 처리
					if (nr < 1) nr = N;
					else if (nr > N) nr = 1;
					if (nc < 1) nc = N;
					else if (nc > N) nc = 1;
				}
				temp[nr][nc].push(cur); // 중복 이동을 막기 위해 temp에 저장
			}
		}
	}

	// 합치고 쪼개기
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
        	// 파이어볼 개수가 2이상인지, 쪼개질 때 각각의 속도 파악하기 위해 size 사용
			int size = temp[r][c].size();
			if (size) {
				if (size >= 2) {
					int m_sum = 0, s_sum = 0, d_sum = 0;
					int flag = 0, post;
					info cur = temp[r][c].front();
					temp[r][c].pop();
					m_sum += cur.m, s_sum += cur.s; d_sum += cur.d;
                    // post에 먼저 짝수 인지 홀수 인지 저장
					post = d_sum % 2;
					while (!temp[r][c].empty()) {
						cur = temp[r][c].front();
						temp[r][c].pop();
						m_sum += cur.m, s_sum += cur.s; d_sum += cur.d;
                        // 방향이 이전 방향과 짝/홀이 다르다면 flag 1로 만들기
						if (post != cur.d % 2) flag = 1;
					}
					if (m_sum >= 5) { // 질량 합이 5이상이 아니면 소멸
						for (int i = 0; i < 4; i++) {
                        	// flag를 1로 만들었으면 1,3,5,7
                            // 그렇지 않으면 2,4,6,8
                            // map에 저장
							map[r][c].push({ m_sum / 5, s_sum / size, 2 * i + flag });
						}
					}
				}
				else { // 파이어볼이 한개 밖에 없으면 그냥 map에 저장
					info cur = temp[r][c].front();
					temp[r][c].pop();
					map[r][c].push({cur});
				}
			}
		}
	}
}

int main() {
	int ans = 0;
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		scanf("%d %d %d %d %d", &r, &c, &m, &s, &d);
		map[r][c].push({ m ,s ,d });
	}
    // K번만큼 move
	for (int i = 0; i < K; i++) {
		move();
	}
    // 남아 있는 파이어볼 질량 합 구하기
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			while (!map[r][c].empty()) {
				info cur = map[r][c].front();
				map[r][c].pop();
				ans += cur.m;
			}
		}
	}
    // 정답 출력
	printf("%d", ans);
	return 0;
}