[C++] 백준 16957번 체스판 위의 공

문제

크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다.

체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다.

인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다.
그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다.
공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을 수 있다. 체스판의 상태가 주어진다. 공이 더 이상 움직이지 않을 때, 각 칸에 공이 몇 개 있는지 구해보자.

입력

첫째 줄에 체스판의 크기 R, C가 주어진다. 둘째 줄부터 R개의 줄에 체스판에 적혀있는 정수가 주어진다.

출력

총 R개의 줄에 걸쳐서 체스판에 적힌 정수를 출력한다.

제한

1 ≤ R, C ≤ 500
0 ≤ 체스판에 적힌 정수 ≤ 300,000

풀이

solve 함수는 체스판의 (x,y)지점에 있는 공이 최종적으로 이동할 위치를 pair로 리턴하는 함수이다. 처음에는 pair를 활용할 생각을 하지못해 많이 헤맸었다.
공이 더이상 이동할 수 없을때까지 8가지 방향중 가장 작은 방향으로 함수를 재귀적으로 호출하여 이동한다. 이를 메모이제이션을 통해 기록하면 해결할 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int r,c;
int board[500][500];
int ans[500][500];
int dx[9] = {-1,-1,-1,0,0,0,1,1,1};
int dy[9] = {-1,0,1,-1,0,1,-1,0,1};

pair<int,int> dp[500][500];

pair<int,int> solve(int x, int y){

  pair<int,int>& pos = dp[x][y];
  if (pos.first != -1) return pos;

  int ret = 300000;
  int dir = -1;
  for (int i=0; i<9; i++){
    int nx = x+dx[i];
    int ny = y+dy[i];

    if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;

    if (ret > board[nx][ny]){
      ret = board[nx][ny];
      dir = i;
    }
  }

  if (dir == 4) {
    pos.first = x;
    pos.second = y;
    return pos;
  }
  else {
    return pos = solve(x+dx[dir],y+dy[dir]);
  }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> r >> c;

  for (int i=0; i<r; i++)
    for (int j=0; j<c; j++)
      cin >> board[i][j];
  
  for (int i=0; i<r; i++)
    for (int j=0; j<c; j++)
      dp[i][j] = make_pair(-1,-1);
  
  for (int i=0; i<r; i++)
    for (int j=0; j<c; j++)
      ans[solve(i,j).first][solve(i,j).second]++;
  
  for (int i=0; i<r; i++){
    for (int j=0; j<c; j++)
      cout << ans[i][j] << " ";
    cout << endl;
  }
}