백준 20057번 마법사 상어와 토네이도 문제 풀이

문제 설명

문제를 보고 든 생각

• 구현 문제이기 때문에 단계별로 함수를 잘 작성하면 되겠다.
• 2차원 배열을 회전시키는 알고리즘을 떠올려야겠다.
• $\alpha$에는 무엇을 넣어야 하나? (원래 있던 모래양 - 이동한 모래)
• 간단하겠다. 개인적으로 제일 성가셨던 구현 문제였다. (토네이도가 한 칸씩 움직인다는 것을 보지 못했다..., $\alpha$에 55%가 들어가는 건 줄 알았다...)

간단한 풀이 설명

1. 토네이도가 움직일 모래의 비율을 저장하는 2차원 배열 tRatio
2. tRatio를 회전시킬 함수 rotateT (tRatio를 회전시키고자 했다.)
3. 토네이도를 r,c로 이동시킬 moveTornado(int r, int c)함수
   • moveTornado는 밖으로 나간 모래 양을 반환한다.
4. tPivot은 N/2 + 1이다. (지도의 가운데)
5. PIVOT은 2이다. (tRatio의 가운데)
6. 대각선을 기준으로 토네이도가 방향을 틀도록 했다. (단 왼쪽 위의 경우는 다른 조건을 주었다.)
7. tDir은 토네이도의 이동 방향을 저장한 변수다.
   • 토네이도가 회전할 때 마다 tDirNum를 하나씩 증가시켰다.
   • 다음 가야할 방향은 tDirNum % 4 로 결정했다.

코드

#include <iostream>

#define MAX_N 500
#define PIVOT 2

using namespace std;


int tDir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
int map[MAX_N][MAX_N];
int tRatio[5][5];
int N;
int tPivot;

void getInput(){
  cin >> N;
  tPivot = N/2 + 1;
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=N; ++c){
      int temp; cin >> temp;
      map[r][c] = temp;
    }
  }
}

void setTRatio(){
  tRatio[PIVOT-2][PIVOT] = 2;
  tRatio[PIVOT+2][PIVOT] = 2;
  tRatio[PIVOT-1][PIVOT+1] = 1;
  tRatio[PIVOT+1][PIVOT+1] = 1;
  tRatio[PIVOT-1][PIVOT] = 7;
  tRatio[PIVOT+1][PIVOT] = 7;
  tRatio[PIVOT-1][PIVOT-1] = 10;
  tRatio[PIVOT+1][PIVOT-1] = 10;
  tRatio[PIVOT][PIVOT-2] = 5;
  tRatio[PIVOT][PIVOT-1] = -1;
}

int moveTornado(int r, int c){
  int outSand = 0;
  int movedSand = 0;
  int currSand = map[r][c];
  int temp[5][5];
  pair<int, int> other;
  for(int i=0; i<5; ++i){
    for(int j=0; j<5; ++j){
      if(tRatio[i][j] == -1){
        other = {i, j};
        continue;
      }
      temp[i][j] = (tRatio[i][j]*currSand)/100;
      movedSand += (tRatio[i][j]*currSand)/100;
    }
  }
  temp[other.first][other.second] = currSand - movedSand;

  for(int i=0; i<5; ++i){
    for(int j=0; j<5; ++j){
      int tempR = r + i-PIVOT, tempC = c + j-PIVOT;
      if(tempR < 1 || tempC < 1 || tempR > N || tempC > N){
        outSand += temp[i][j];
        continue;
      }
      map[tempR][tempC] += temp[i][j];
    }
  }
  map[r][c] = 0;

  return outSand;
}

void rotateT(){
  int temp[5][5];
  for(int r=0; r<5; ++r){
    for(int c=0; c<5; ++c){
      temp[5-c-1][r] = tRatio[r][c];
    }
  }
  for(int r=0; r<5; ++r){
    for(int c=0; c<5; ++c){
      tRatio[r][c] = temp[r][c];
    }
  }
}

int solution(){
  getInput();
  setTRatio();
  int tDirNum = 0;
  int r = tPivot, c = tPivot - 1; // tornado start position
  int outSand = 0;
  int stop = 0;
  while((r != 1 || c != 1)){
    outSand += moveTornado(r, c);
    if((r - tPivot - 1 == c - tPivot) && (c - tPivot < 0)){
      rotateT();
      ++tDirNum;
    } else if((abs(r - tPivot) == abs(c - tPivot)) && (r - tPivot > 0 || c - tPivot > 0)){
      rotateT();
      ++tDirNum;
    }

    r += tDir[tDirNum%4][0];
    c += tDir[tDirNum%4][1];
  }
  outSand += moveTornado(1, 1);
  
  return outSand;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << solution();

  return 0;
}

후기

• 문제를 똑바로 읽자.
• 그리고 구현 문제를 너무 간단한게 생각하지 말자.
• 하면서 토 오억번 함