for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
temp[j][i] = board[i][n - 1 - j];
}
}이 문제는 캐시를 활용해서 좀 더 쉽게 구현이 가능할 것 같은데, 캐시보다 내가 직접 구현하는게 마음이 편해서 그냥 구현했다. 물론 캐시를 이용하면 코드의 양이 줄고 실수가 줄을 텐데... 사실은 캐시를 제출하고 생각하게 됐다. 캐시를 하게 되면 다시 rotate를 하지 않아도 될텐데!
그리고 이 문제는 어느 특정 위치에서 rotate를 할때 발생하는 착오가 굉장히 많이 생겨난다. 오늘은 그것을 정리해볼 것이다.
특정 위치에서 시계방향 또는 반시계방향을 돌리는 것이 이 문제 해결의 주요 쟁점이 될 것이다.
천천히 정리를 해보겠습니다.
일단 기본적인 시계방향 전환입니다. 시작 위치는 (0,0)이고 배열의 범위는 n - 1 입니다.
void cw() {
int temp[MAX][MAX];
memset(temp,0,sizeof(temp));
// 시계방향 회전
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
temp[i][j] = board[n - 1 - j][i];
}
}
}시계방향 회전할때를 천천히 생각해봅시다.
1행 마지막 열을 1열 1행부터 차례대로 옮겨야 합니다. 즉, (n - 1, 0) -> (0, 0) 으로 옮기는 과정이 필요합니다.
계속해서 이어나가면?
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)
위 배열을 변화시켜줘야한다.
(3,0) (2,0) (1,0) (0,0)
(3,1) (2,1) (1,1) (0,1)
(3,2) (2,2) (1,2) (0,2)
(3,3) (2,3) (1,3) (0,3)
이런식으로 계속해서 이루어지는 과정이 temp[i][j] = board[n - 1 - j][i] 가 됩니다. 이 내용을 보면? 변화해야하는 값과 옮기는 당시 변화하지 않는 값이 존재하게 되겠지요?
(1) temp에서는 열이 변화하지 않습니다. 옮겨야될 board에선 x가 변화하지 않습니다.
(2) temp에서는 행이 변화합니다. 옮겨야될 board에선 y가 변화합니다. 이처럼 이중 포문에서 변화할 부분과 변화하지 않는 부분이 딱 정해져 있습니다. 이렇게 생각하면, 어디서든 회전이 가능할 것입니다.
처음 시작하는 위치 (y,x)를 알고, 돌려야할 범위를 알 수 있다면? 문제를 해결할 수 있을 것 입니다.
하지만, 처음 시작하는 위치와 그 범위가 매번 다르게 나온다면 당연히 위의 알고리즘도 바뀔 수 밖에 없습니다.
여기서 중요한 부분은 1씩 이동하면서 계속해서 옮겨주는 과정을 거듭하면 된다는 것입니다. 하지만 시작위치가 바뀌는 것 만큼 다양하게 바꿔서 작성을 해야할 필요가 있습니다.
우리는 시작위치는 (y,x) 그리고 범위는 3으로 지정을 할 예정이다.
temp에 작성되는 부분은 변경할 필요가 없다. 왜냐하면 그대로 순차적으로 순회하면서 저장하면 되기 때문이다.
하지만, 다른 부분은 변경해주어야한다.
열은 맨 아래에서 차례차례위로 올라와야 하기 때문에 계속해서 바뀌는 내부 포문에서 - j를 하면서 올라가준다. 하지만 이것은 (0,0)일때만 가능한 방법이다. 0부터 ~ 범위까지 하나씩 올라가니까.
하지만 (2,2)일때는 내용이 달라진다 2+3-1이 범위인데 4에서 x의 값이 2이기에 4-2, 4-3 이런식으로 올라간다.
우리는 4-0, 4-1, 4-2 이런식으로 올라가서 끝나야하는데 말이다. 그래서 우리는 첫 시작을 더해주면 0이되어 이러한 문제를 해결할 수 있지 않을까 생각을 해보았다. 그렇다 역시나 맞았다.
그다음은 행에 대한 처리이다. 행 또한 (0,0)이라면 문제가 되지 않는다. 차례로 저장해주면 되니까.
하지만 x의 위치가 변화했고, 변화한 x위치에서 +1, +2 씩 이동해야하기 때문에 그 값을 어디서 구할까? 우리는 외부 포문에서 내부 포문이 이동을 전부할때까지 변화하지 않아서 i - y를 해주면 처음에 0이되고 계속해서 x 위치에서 +1 씩 증가하게 되지 않을까? 역시나 맞았다 아래는 어느위치에서도 허용가능한 코드이다.
int range = y + 3 - 1;
for(int i = y; i < y + 3; i++){
for(int j = x; j < x + 3; j++){
temp[i][j] = tempBoard[range - j + x][i - y + x];
}
}위와같이 변경하면 어디서든 바꿀 수 있는 코드가 완성된다. 약간의 고민이 필요한 내용이였다. 위 범위 기준은 달라질 수 있기에 그 점만 명심하면 될 것같습니다.
이제는 반대 전환상황을 보도록 하겠습니다.
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)
을 반대전환하는 것입니다. 시계 반대방향으로
(0,3) (1,3) (2,3) (3,3)
(0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1)
(0,0) (1,0) (2,0) (3,0)
이런식으로 원래 배열에서 우측에서 좌측으로 한칸씩 이동하면서
바꿔질 배열에는 위측에서 아래쪽으로 한칸씩 이동하면서 저장해주면 됩니다.
바꿔질 배열은 첫행에서 아래로 내려오면서 배열에 저장하게 되고, 원형에서는 마지막 열에서 차례로 첫번째 열까지 이동하면서 한칸씩 이동하면서 배열을 파악한다.
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
temp[j][i] = board[i][n - 1 - j];
}
}이렇게 하면 배열이 반대로 돌아가게 된다. 위의 내용과 같으며, 생각만 조금 바꿔주면 된다. 하지만 이건 특정 위치에서 반대시계방향 이동이 굉장히 굉장히 생각할게 많다. 천천히 정리를 해보겠다.
바뀌는 것과 안바뀌는 것 부터 차례로 얘기를 해야된다.
바뀌지 않는것
1. 원형 배열에서 y열은 늘 똑같다. 바뀌지 않는다. n부터 n + range까지 이어나간다.
바뀌는 것
1. 원형 배열에서 x행은 계속해서 바뀐다.
(1) x위치에서 + range - 1은 범위가 될 것이다.
(2) 하나하나씩 좌측으로 이동하면서 검사를 해야한다.
(3) 하지만 x의 값이 2라면 어떻게 될까? -2부터 시작하게 되므로 문제가 된다.
(4) 우리는 0을 만들어줘야하기 때문에 -2인 초기 x값만큼을 더해주면서 문제를 해결한다.
2. 바뀌는 배열에서 y열은 계속해서 바뀐다.
(1) Y의 위치는 초기 위치와 동일하기 때문에 y를 넣어준다.
(2) y의 값이 +1씩 증가면서 아래로 내려가야한다.
(3) 그렇게 하기 위해선 내부 for문을 이용해야한다.
(4) 내부 for문은 x를 옮기는 값이다.
(5) x를 이용해서 0, +1, +2 를 만들어야한다.
(6) 그렇게 하기 위해선 초기 위치 j에서 x를 빼주면 그 값이 허용된다.
3. 바뀌는 배열에서 x열은 계속해서 변화한다.
(1) x의 값은 계속해서 변화하진 않지만, 위치는 갱신해줘야한다.
(2) 현재 내부 for문이 x를 담당하고 있기 때문에, 여기에서 계속 변화를 주는 것은 말이 안된다.
(3) x은 그대로 존재하고, 내부 for문이 모두 종료하게 되면 한칸 이동하게 되어야 한다.
(4) 그것은 외부에 존재하는 i로 결정지을 수 있다.
(5) i는 계속해서 증가하고 초기 y의 값은 고정이다. 그렇게 0, +1, +2, +3을 만들 수 있다.
코드는 이러하다.
for(int i = y; i < y + 3; i++){
for(int j = x; j < x + 3; j++){
temp[j - x + y][i - y + x] = board[i][x + 3 - 1 - j + x];
}
}
아래는 정답 코드이다. 위의 문제만 잘 해결할 수 있다면? 문제를 쉽게 풀이할 수 있었다. 캐시를 이용해서 문제도 해결해보아야겠다. 모든 9개를 다시 돌리는것은 분명히 문제가 있다. 그리고 BFS로 최대 n*n 만큼 돌리는 것 또한!
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#define MAX 7
using namespace std;
/*
유적지의 범위는 5이므로 범위 5안에서 논다.
그래서 범위를 7로 지정해두고, range는 5로 지정을 해두었다.
*/
queue<int> q;
int n = 5,repeat,blockCount,board[MAX][MAX],visited[MAX][MAX];
// 자주사용하는 함수를 정리하자.
// 1. bfs를 사용할떄 돌리는 함수
int isRange(int y, int x){
return 0 <= y && y < n && 0 <= x && x < n;
}
// 2. 변형된 board를 파악하는 함수
void printBoard() {
cout << "print board!" << "\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << board[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
}
void init() {
cin >> repeat >> blockCount;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
cin >> board[i][j];
}
}
for(int i = 0; i < blockCount; i++){
int num; cin >> num;
q.push(num);
}
}
// 1. board를 계속해서 사용해야하기 때문에 보존을 해야한다.
// 2. tempBoard를 사용해야한다.
int temp[MAX][MAX]; // 임시로 rotate를 하고나서 얘를 이용해서 bfs를 돌리자.
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
struct INFO {
int y;
int x;
int rotateRepeat;
int total;
};
vector<INFO> bestRotateadLocation;
bool comp(INFO& a, INFO& b){
if(a.total == b.total){
if(a.rotateRepeat == b.rotateRepeat){
if(a.x == b.x){
return a.y < b.y;
}
return a.x < b.x;
}
return a.rotateRepeat < b.rotateRepeat;
}
return a.total > b.total;
}
int bfs(int y, int x) {
queue<pair<int,int> > q;
q.push({y,x});
// 현재 이 값은 temp에서 놀고있다.
// 전역변수로 만들어서 temp에서 놀고있는데, 원래는
// &을 사용해서 지정된 위치에서만 놀게해야한다.
// 근데 범위를 벗어나지 않으니 뭐 그닥?
int cnt = 1;
int color = temp[y][x]; // 우리는 temp에서 노는거다.
visited[y][x] = 1;
while(!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
// 범위를 벗어나거나
if(!isRange(ny,nx)) continue;
// 방문을 했다거나?
if(visited[ny][nx]) continue;
// 이동할 값이 색이 다르다거나?나는 색깔로 정했다.
if(temp[ny][nx] != color) continue;
// 위 조건을 전부 충족하지 않는 녀석들은 그룹이 될 자격이
// 있다.
cnt++;
visited[ny][nx] = 1;
q.push({ny,nx});
}
}
// 3개 이상은 그룹으로 간주해, cnt를 return한다.
if(cnt >= 3) return cnt;
else return 0;
}
// 우리는 rotate를 돌릴건데, 문제가 무엇이냐면?
// board의 값은 변하면 안된다 그래서, tempBoard에 board를 cpy한다.
// temp에 board를 cpy한다.
void rotate(int y, int x, int rotateRepeat) {
int tempRotateRepeat = rotateRepeat;
int tempBoard[MAX][MAX]; // 임시 Board로 복사를 한다.
int tempRotate[MAX][MAX];
memset(visited,0,sizeof(visited)); // rotate돌리고, visited처리하고
memcpy(tempBoard, board, sizeof(board));
memcpy(temp, board, sizeof(board));
// 격자의 범위는 누구나 알겠지?
int range = y + 3 - 1;
while(tempRotateRepeat--) {
// 시작위치를 기준으로 잘 생각해야한다.
// 물론 역시계방향이 더 어렵다 생각하기에, 그것도 작성해보자.
for(int i = y; i < y + 3; i++){
for(int j = x; j < x + 3; j++){
temp[i][j] = tempBoard[range - j + x][i - y + x];
}
}
for(int i = y; i < y + 3; i++){
for(int j = x; j < x + 3; j++){
tempBoard[i][j] = temp[i][j];
}
}
}
// 회전을 원하는 만큼 시켰다면?
// 1. bfs를 시작한다.
// 2. 최대 유물 개수를 구한다.
int totalBlockCount = 0;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
if(!visited[i][j]){
// 그룹을 찾아서 3이상이면 개수를 구하는 문제이다.
totalBlockCount += bfs(i,j);
}
}
}
// 어쩄든 총 개수가 나와줬다면? 그 기준위치는 중간이기에 +1씩 해주고, 방향전환과 총 개수를 세어린다.
if(totalBlockCount) { // 가운데가 기준, 반복횟수, 총 유물의 개수
bestRotateadLocation.push_back({y + 1, x + 1, rotateRepeat, totalBlockCount});
}
}
bool comp2(pair<int,int>& a, pair<int,int>& b) {
if(a.second == b.second){
return a.first > b.first;
}
return a.second < b.second;
}
vector<pair<int,int> > findBlock;
int boardBFS(int y, int x) {
vector<pair<int,int> > tempFindBlock;
queue<pair<int,int> > q;
q.push({y,x});
int cnt = 1;
int color = board[y][x];
tempFindBlock.push_back({y,x});
visited[y][x] = 1;
while(!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(!isRange(ny,nx)) continue;
if(visited[ny][nx]) continue;
if(board[ny][nx] != color) continue;
cnt += 1;
tempFindBlock.push_back({ny,nx});
visited[ny][nx] = 1;
q.push({ny,nx});
}
}
if(cnt >= 3){
for(int i = 0; i < tempFindBlock.size(); i++){
int blockY = tempFindBlock[i].first;
int blockX = tempFindBlock[i].second;
findBlock.push_back({blockY, blockX});
}
return cnt;
} else {
return 0;
}
}
// 무한 반복하러 왔습니다.
void rotateBoard(int y, int x, int rotateNumber) {
int tempBoard[MAX][MAX]; // 임시 Board로 복사를 한다.
int tempRotate[MAX][MAX];
// 사실 이렇게나 필요하진 않다.
// tempBoard[MAX][MAX] 이거 하나만 있으면 된다.
memcpy(tempBoard, board, sizeof(board));
memcpy(temp, board, sizeof(board));
int range = y + 3 - 1;
while(rotateNumber--) {
for(int i = y; i < y + 3; i++){
for(int j = x; j < x + 3; j++){
temp[i][j] = tempBoard[range - j + x][i - y + x];
}
}
for(int i = y; i < y + 3; i++){
for(int j = x; j < x + 3; j++){
tempBoard[i][j] = temp[i][j];
}
}
}
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
board[i][j] = temp[i][j];
}
}
// 1. bfs
// total값은 계속해서 더해진다.
int result = 0;
// 반복을 해준다.
while(1) {
// visited 안되는지 확인하기, visited된것을 제거해야한다.
// findBlock 없애주기. 계속해서 돌려하기 때문이다.
memset(visited,0,sizeof(visited));
findBlock.clear();
// 전체적으로 bfs를 통해서 result가 몇인지 확인하자
// 사실 위 과정을 안겪고 싶은데, 시초나면 캐시하자.
// 3차원 배열 사용해서 캐시하면 되니까
// 그리고 이어서 나온 위치도 캐시하면 되니까
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(!visited[i][j]) {
result += boardBFS(i,j);
}
}
}
// 2. block sort
// findBlock이 생긴다면, sort해주고 처리해준다.
if(findBlock.size()){
sort(findBlock.begin(), findBlock.end(), comp2);
} else{
// 결과값이 나오고
cout << result << " ";
break;
}
// 3. sorted Block
// 저만큼 board에서 지워주는데, 유물의 개수를 모자람이 없다니까
// 무식하게 이렇게 해주자.
for(int i = 0; i < findBlock.size(); i++){
int number = q.front();
q.pop();
board[findBlock[i].first][findBlock[i].second] = number;
}
//printBoard();
}
}
int findRotateSearch() {
// 최고의 유적지 위치를 찾기 위해서 그 값을 비워준다.
bestRotateadLocation.clear();
// 최적의 유적지 위치의 중심부는
// y의 범위는 3, x의 범위도 마찬가지로 3이 된다.
// (1,1) ~ (3,3) 범위의 값이 중앙 위치가 되므로 전부 -1,-1해주어서 구한다.
// 그리고 회전은 3번까지 가능하기에 저렇게 돌려준다.
for(int i = 0; i <= 2; i++){
for(int j = 0; j <= 2; j++){
for(int r = 1; r <= 3; r++){
rotate(i,j,r);
}
}
}
// 위 과정이 전부 종료가 된다면?
// 유적지가 생기는 방법이 여러가지가 나오거나 안나오거나이다.
// 나온다면?
if(bestRotateadLocation.size()) {
// 최고의 우선순위를 찾아낸다.
sort(bestRotateadLocation.begin(), bestRotateadLocation.end(), comp);
// 이제 진짜 board를 회전하러 가야한다. (-1,-1)씩 제거해주자.
rotateBoard(bestRotateadLocation[0].y - 1, bestRotateadLocation[0].x - 1, bestRotateadLocation[0].rotateRepeat);
return 1; // 무엇이라도 나왔다면? 무한 반복하러 가야한다.
} else{
// 나오지 않았다면? 종료해야한다.
return 0; // 어떠한 값도 나오지 않았다면 그냥 종료해야한다.
}
}
void solve() {
// 총 반복횟수만큼 최적의 유적지 회전 위치를 찾을 것이다.
// 하지만, 발견된것이 없다면? 바로 종료시켜주는 방향으로 가겠다.
while(repeat--){
// 그래서 false가 나오면 종료가 된다.
if(!findRotateSearch()) break;
}
}
int main() {
init();
solve();
return 0;
}'PS > CodeTree' 카테고리의 다른 글
| [기출문제] 마법의 숲 탐색 (0) | 2024.09.29 |
|---|