[PS]맞왜틀 시리즈2 좌표처리, 마법사 상어와 파이어볼

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다.

우리는 그럴때 이렇게 말한다.

백준 20056번 마법사 상어와 파이어볼 문제를 풀며 틀렸던 내용입니다.

기본적인 문제에 대한 설명과 해설은 레퍼런스에서 참고합니다.

 

이 글을 쓴 이유는 좌표처리 하며 생긴 생각의 오류를 남기기 위해서입니다.

 

마법사 상어가 쏜 파이어볼은 주어진 좌표체계에서 상하좌우 사방대각선으로 0에서 8까지의 방향으로 아래의 그림과 같이 움직입니다.

 

행을 y축 열을 x축이라고 생각했을때 각 방향으로의 좌표 변화는 다음과 같이 표현할 수 있습니다.

dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
dy = { 1, 1, 0, -1, -1, -1, 0, 1 };

그런데 문제가 발생합니다. 디버깅을 해보니 파이어볼이 위아래가 뒤집혀서 움직입니다.

저는 파이어볼을 좌표위치별로 담는 벡터 배열을 선언했는데 좌표변화에 따라서 배열 인덱스는 위로 가려면 -1 아래로 가려면 +1을 해야합니다. 평상시 생각하는 좌표 체계와 반대 방향이었던 거죠. 즉, 아래와 같아야 합니다.

dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
dy = { -1, -1, 0, 1, 1, 1, 0, -1 };

좌우에 해당하는 dx 는 똑같습니다. 위아래에 해당하는 dy가 반대입니다.

해당 문제에 대한 풀이를 찾아봤으나 이동 방향에 대한 이해가 잘 되지 않는 분들에게 도움이 되길 바랍니다.

 

 

문제

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

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

문제풀이

https://na982.tistory.com/132?category=145346 

[삼성 SW 역량 테스트] 마법사 상어와 파이어볼

 

전체코드

//https://www.acmicpc.net/problem/20056
#include <stdio.h>
#include <vector>
using namespace std;
/*
 
마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다.
i번 파이어볼의 위치는(ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다.위치(r, c)는 r행 c열을 의미한다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 
1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
-> 좌표 순환
파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.
7 0 1
6   2
5 4 3
*/
int dc[8] = { 0, 1, 1, 1, 0, -1, -1 , -1 };
int dr[8] = { -1, -1, 0, 1, 1 , 1, 0, -1 };
/*
마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.
모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
*/
/*
마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.
*/
/*
4 ≤ N ≤ 50
0 ≤ M ≤ N^2
1 ≤ K ≤ 1,000
1 ≤ ri, ci ≤ N
1 ≤ mi ≤ 1,000
1 ≤ si ≤ 1,000
0 ≤ di ≤ 7
*/
//N = 격자크기, M = 파이어볼 수
int N, M, K;
 
 
struct fireballInfo {
    //(r행,c열) 위치, m 질량, d 방향, s 속력
    int r, c, m, s, d;
};
vector<fireballInfo> map[51][51];
vector<fireballInfo> ball;
 
//Move fireball until fireball list is empty
void move() {
    //buf for saving next fireball information
    vector<fireballInfo> nextMap[51][51];
    fireballInfo current;
    int S;
    //check ball list
    while (!ball.empty()) {
        current = ball.back();
        ball.pop_back();
        //Modulation of Speed
        S = current.s % N;
        //Calculate coordinate
        current.c = ((current.c - 1) + (dc[current.d] * S + N)) % N + 1;
        current.r = ((current.r - 1) + (dr[current.d] * S + N)) % N + 1;
        nextMap[current.r][current.c].push_back(current);
    }
    //copy nextMap to origin map
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            map[r][c] = nextMap[r][c];
        }
    }
}
/*
이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
파이어볼은 4개의 파이어볼로 나누어진다.
나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
질량이 0인 파이어볼은 소멸되어 없어진다.
*/
 
void mergeAndDivide() {
    fireballInfo nextFireball;
    //check how many balls are in the location of map
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            int even = true, odd = true, M = 0, S = 0;
            if (map[r][c].size() == 0)
                continue;
            if (map[r][c].size() == 1) {
                ball.push_back(map[r][c][0]);
                continue;
            }
            //merge mass fireballs if there are two or more
            for (int b = 0; b < map[r][c].size(); b++) {
                M += map[r][c][b].m;
                S += map[r][c][b].s;
                if (map[r][c][b].d % 2 == 0)
                    odd = false;
                else
                    even = false;
            }
            //Divide a ball into four with mass, direction and speed
            nextFireball.r = r;
            nextFireball.c = c;
            nextFireball.m = M / 5;
            int cnt = map[r][c].size();
            if (nextFireball.m == 0)
                continue;
            nextFireball.s = S / cnt;
            for (int i = 0; i < 4; i++) {
                if (odd || even)
                    nextFireball.d = i * 2;
                else
                    nextFireball.d = i * 2 + 1;
                ball.push_back(nextFireball);
            }
        }
    }
    
}
int solve() {
    for(int m = 0; m < K; m++){
        move();
        mergeAndDivide();
    }
    int sum = 0;
    for (int b = 0; b < ball.size(); b++) {
        sum += ball[b].m;
    }
    return sum;
}
int main() {
    int result = -1;
    //Input
    fireballInfo tmp;
    /*
    입력
    첫째 줄에 N, M, K가 주어진다.
    둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다.파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.
 
    출력
    마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.
    */
    scanf("%d %d %d", &N, &M, &K);
    for (int m = 0; m < M; m++) {
        scanf("%d %d %d %d %d", &tmp.r, &tmp.c, &tmp.m, &tmp.s, &tmp.d);
        ball.push_back(tmp);
    }
 
    //--------------------Solution--------------
    result = solve();
 
    //Output
    printf("%d", result);
 
    return 0;
}