[BOJ] 20057 : 마법사 상어와 토네이도 (C++)

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

걸린 시간 : 54분 26초

---

삼성의 상어 시리즈 문제이다. 정말 구현! 이다.

알고리즘

모래밭을 주어진 형태로 계속 돌면서 흩뿌리면 된다. 움직이는 기능을 하는 함수인 move()와 흩뿌리는 기능을 하는 함수인 scatter()만 구현하면 된다.

움직이기

move(int ci, int cj, int dir, int leftcnt) 함수는 현재 위치에서 현재 방향으로 한 칸 움직이는 함수이다. 단, 남은 횟수가 더 이상 없다면 실행을 멈추거나 방향을 바꿔서 직진한다.

여기서 방향은 di, dj 배열에 좌, 하, 우, 상 순으로 넣어놨다. 따라서 반시계 방향으로 회전하려면 단순히 dir = (dir + 1) % 4; 만 실행하면 된다.

또한 남은 횟수 지정은 다음과 같은 규칙을 보면 쉽게 일반항을 생각할 수 있다. (처음 이동할 때 방향은 이미 한 번 바꾼 것으로 생각)

방향 1번 바꿈 -> 1칸 전진
방향 2번 바꿈 -> 1칸 전진
방향 3번 바꿈 -> 2칸 전진
방향 4번 바꿈 -> 2칸 전진
방향 5번 바꿈 -> 3칸 전진
...
방향 N번 바꿈 -> (N+1) / 2 칸 전진

따라서 현재 방향을 바꾼 횟수를 기반으로 다음 전진할 횟수를 다음과 같이 정했다.

int nextcnt = (changecnt + 1) / 2;

하지만 마지막 맨 윗줄을 왼쪽으로 달리는 때에는 (N+1) / 2 칸을 전진하는 것이 아닌 N / 2 칸을 전진하게 된다.

if (nextcnt == N) nextcnt = changecnt / 2;

흩뿌리기

scatter(int i, int j, int dir) 함수는 어떤 지점으로 전진할 때 모래를 흩뿌리는 함수이다.

여기서 보는 방향의 반시계, 시계 방향으로 회전한 곳까지도 모래를 흩뿌리기 때문에 반시계 방향으로 한 번 회전한 nextdir 과 시계 방향으로 한 번 회전한 predir을 계산해 흩뿌리는 지점을 계산했다.

하지만 문제를 풀고 보니 너무 중복되는 호출이 많아 반복문을 활용했어야 했던 것 같다.

자세한 내용은 밑의 코드에 있다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
 
int N, answer;
int changecnt;
int board[500][500];
int di[4] = {0, 1, 0, -1};
int dj[4] = {-1, 0, 1, 0};
 
void addsand(int i, int j, int amount) {
    if (i < 0 || i >= N || j < 0 || j >= N) {
        answer += amount;
        return;
    }
    board[i][j] += amount;
}
 
void scatter(int i, int j, int dir) {
    int minus = 0;
    int nextdir = (dir + 1) % 4;
    int predir = (dir + 3) % 4;
    addsand(i + 2*di[dir], j + 2*dj[dir], board[i][j] / 20);
    minus += board[i][j] / 20;
    addsand(i + di[dir] + di[nextdir], j + dj[dir] + dj[nextdir], board[i][j] / 10);
    minus += board[i][j] / 10;
    addsand(i + di[dir] + di[predir], j + dj[dir] + dj[predir], board[i][j] / 10);
    minus += board[i][j] / 10;
    addsand(i + di[nextdir], j + dj[nextdir], board[i][j] * 7 / 100);
    minus += board[i][j] * 7 / 100;
    addsand(i + di[predir], j + dj[predir], board[i][j] * 7 / 100);
    minus += board[i][j] * 7 / 100;
    addsand(i + 2*di[nextdir], j + 2*dj[nextdir], board[i][j] / 50);
    minus += board[i][j] / 50;
    addsand(i + 2*di[predir], j + 2*dj[predir], board[i][j] / 50);
    minus += board[i][j] / 50;
    addsand(i - di[dir] + di[nextdir], j - dj[dir] + dj[nextdir], board[i][j] / 100);
    minus += board[i][j] / 100;
    addsand(i - di[dir] + di[predir], j - dj[dir] + dj[predir], board[i][j] / 100);
    minus += board[i][j] / 100;
    addsand(i + di[dir], j + dj[dir], board[i][j] - minus);
    board[i][j] = 0;
}
 
void move(int ci, int cj, int dir, int leftcnt) {
    leftcnt--;
    int ni = ci + di[dir];
    int nj = cj + dj[dir];
    scatter(ni, nj, dir);
    if (leftcnt == 0) {
        if (changecnt == 2 * N - 1) {
            return;
        }
        changecnt++;
        dir = (dir + 1) % 4;
        int nextcnt = (changecnt + 1) / 2;
        if (nextcnt == N) nextcnt = changecnt / 2;
        move(ni, nj, dir, nextcnt);
    }
    else {
        move(ni, nj, dir, leftcnt);
    }
}
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    changecnt++;
    int si = N/2, sj = N/2, dir = 0;
    move(si, sj, dir, 1);
    cout << answer;
    return 0;
}