[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;
}
}
Author And Source
이 문제에 관하여([C++] 백준 16957번 체스판 위의 공), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lacram/C-백준-16957번-체스판-위의-공저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)