typedef pair<int, int> pos;
static int N, M, K;
static int board[2][100][100];
static int direction[2][100][100];
static int tmp[100][100];
static queue<pos> q;
static int d[5][2] = {
0, 0,
-1, 0, //상, 실수했던 부분,
1, 0, //하, //
0, -1, //좌
0, 1 //우
};
static int changed[5] = { 0, 2, 1, 4, 3 };
static int solution(void)
{
int y, x, nr, dir;
int turn = 0, ret = 0;
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < K; i++)
{
scanf("%d %d %d %d", &y, &x, &nr, &dir);
q.push({ y, x });
board[turn][y][x] = nr;
direction[turn][y][x] = dir;
}
for (int h = 0; h < M; h++)
{
int q_sz = q.size();
for (int cnt = 0; cnt < q_sz; cnt++)
{
pos cur = q.front();
q.pop();
dir = direction[turn][cur.first][cur.second];
int ny = cur.first + d[dir][0];
int nx = cur.second + d[dir][1];
if (ny == 0 || ny == N - 1 || nx == 0 || nx == N - 1) //약품으로 칠해진 셀,
{
board[turn][cur.first][cur.second] /= 2;
direction[turn][cur.first][cur.second] = changed[dir];
}
if (!tmp[ny][nx]) //비어있었다면,
q.push({ ny, nx });
if (board[turn][cur.first][cur.second] > tmp[ny][nx]) //군집의 수가 더 큰 경우
{
tmp[ny][nx] = board[turn][cur.first][cur.second];
direction[1 - turn][ny][nx] = direction[turn][cur.first][cur.second];
}
board[1 - turn][ny][nx] += board[turn][cur.first][cur.second]; //누적,
}
memset(board[turn], 0, sizeof(board[turn]));
memset(direction[turn], 0, sizeof(direction[turn])); //오타가 있었던 부분,
memset(tmp, 0, sizeof(tmp));
turn = 1 - turn;
}
while (q.size())
{
pos cur = q.front();
q.pop();
ret += board[turn][cur.first][cur.second];
}
memset(board[turn], 0, sizeof(board[turn]));
memset(direction[turn], 0, sizeof(direction[turn]));
return ret;
}먼저 좌표를 이동 시키는 부분에서 실수가 있었다.
상, 하 에서 착각을 해서 y좌표에 1더하는 것을 위로 올라가는 경우로 처리했었다.
실수하지 말아야할 부분이다.
이어서 문제 풀이에 대해 설명하자면
board는 각 위치에서 군집의 수를 표현하고, direction은 군집의 이동방향을 표현한다.
시간이 흐르면서 이 정보는 변하기 때문에, 3차원 배열로 선언하여 처리하였다.
시간이 0 부터 M - 1 까지, 총 M시간이 흐르는 것을 모델링 하였다.
먼저 약품으로 칠해진 셀로 이동한 경우를 처리한다.
위 그림에서 화살표 1, 2는 상단, 하단 전부 약품으로 칠해진 셀이고, 이 때 y 는 0, (4 - 1) 이다.
화살표 3, 4는 좌측, 우측 전부 약품으로 칠해진 셀을 나타낸다. 이 때 x 는 0, (4 - 1) 이다.
즉, 이동할 y 나 x가 이와 같은 경우라면 현재 군집의 미생물 수를 절반으로 낮추고, 그 방향을 바꾼다.
그 다음 tmp는 해당 좌표의 visit정보 겸, 미생물 수의 최대값 검출을 위해 쓰인다.
여러 군집이 같은 좌표로 향하는 경우, 큐에 중복된 좌표를 푸쉬하지 않게 하기 위함과,
여러 군집 중 미생물 수가 가장 많은 군집의 이동 경로로 설정하기 위함이다.
그리고 다음 시간대에 사용할 해당 좌표에서의 미생물 수를 누적하여, 여러 군집이 합쳐진 것을 표현 할 수 있다.
그리고 오타가 있었던 부분에서는
memset(direction[turn], 0, sizeof(direction))으로 작성했었다.
그래서 처음에는 원하는 흐름대로 잘 되었지만, 그 다음 시간대에서는 이동할 방향의 인덱스가 0 이어서 미생물 군집이 이동하지 않아서 답이 틀리는 문제가 있었다.
사소한 실수 였는데, 이를 늦게 발견했다면 엉뚱한 곳에서 시간을 낭비하고 있을 뻔 했다.
주의해야 할 부분이다.
//
원래 생각은 priority_queue를 이용한 것이다.
priority_queue pqs[100][100];
이렇게 만들어서, 각 좌표에서 큐에 2개 이상의 군집이 있다면, 이 중 top 군집의 방향을 따라가는 식으로 하는 것이었다.
