문제에 명시된 대로 (x1, y1) ~ (x2, y2) 범위를 시계방향으로 회전시킨 후, 회전된 값들 중에서 가장 작은 값을 찾아내는 문제다. 단순 빡구현 문제.
처음에 문제를 보자마자 살짝 겁을 먹었으나, 하나하나 천천히 살펴보면서 구현하니까 생각보다 어렵지 않은 문제였다.
어떻게 하면 시계방향으로 돌릴 수 있을까?
하나의 큰 직사각형 혹은 정사각형을 4 부위로 나눠서 옮기기로 생각했다.
1. 왼쪽에 있는 사각형 옮기기
가장 왼쪽에 있는 사각형 부터 한 칸씩 위로 올려주면 된다. 이때 주의할 점이 있는데 가장 처음 지점 [x1][y1]을 temp라는 임시공간에 저장해둔다. 이러한 이유는 있다가 살펴보고 우선 한 칸씩 이동한다는 점에서 생각하는 것이다.
(2, 2) <- (3, 2) 로
(3, 2) <- (4, 2) 로
(4, 2) <- (5, 2) 로
규칙을 보면, (row, column)에서 column은 y1으로 고정되어 있고, row 값만 변동되는 것을 알 수 있다.
for(int i = x1; i < x2; i++) {
board[i][y1] = board[i+1][y1];
}
2. 아래쪽에 있는 사각형 옮기기
한 번만 더 생각해보자. 빨간색 화살표는 아래 지점의 사각형들을 한 칸씩 옮기는 과정이다.
(5, 2) <- (5, 3)
(5, 3) <- (5, 4)
규칙을 찾았는가? row가 x2로 고정되어 있고, column만 변동하고 있다.
for(int i = y1; i < y2; i++) {
board[x2][i] = board[x2][i+1];
}
3. 오른쪽에 있는 사각형 옮기기
살짝의 순서만 바뀌고 규칙만 찾으면 쉽게 해결할 수 있다.
for(int i = x2; i > x1; i--) {
board[i][y2] = board[i-1][y2];
}
4. 위쪽에 있는 사각형 옮기기
for(int i = y2; i > y1; i--) {
board[x1][i] = board[x1][i-1];
}
아까 저장했던 temp 임시 공간에 저장된 수는 다 옮기고 나서 마지막에 넣어준다.
이유는 한 칸씩 밀렸을 때 board [x1][y1+1] 은 board [x1][y1]으로 덮혀씌워지게 되는데 처음에 왼쪽 사각형부터 옮겼으므로 board[x1][y1] 값은 이미 board[x1+1][y1] 값으로 갱신된다. 따라서 기존에 임시 공간에 저장해둔 board[x1][y1] 수를 board [x1][y1+1]에 넣어주는 것이다.
board[x1][y1+1] = temp;
이렇게 행렬을 시계방향으로 옮기고 나서, 문제에서 요구한 가장 작은 숫자를 찾는 방법은 어떻게 할까?
처음에 temp의 값을 변수에 넣어주고, 이후에 회전을 할 때마다 그 값과 비교해서 min 값을 갱신해주면 된다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
vector<vector<int> > board(rows + 1, vector<int>(columns + 1));
for(int i = 1; i <= rows; i++) {
for(int j = 1; j <= columns; j++) {
board[i][j] = ((i-1) * columns + j);
}
}
vector<int> answer;
for(int i = 0; i < queries.size(); i++) {
int x1 = queries[i][0];
int y1 = queries[i][1];
int x2 = queries[i][2];
int y2 = queries[i][3];
int temp = board[x1][y1];
int num = temp;
for(int i = x1; i < x2; i++) {
board[i][y1] = board[i+1][y1];
num = min(num, board[i][y1]);
}
for(int i = y1; i < y2; i++) {
board[x2][i] = board[x2][i+1];
num = min(num, board[x2][i]);
}
for(int i = x2; i > x1; i--) {
board[i][y2] = board[i-1][y2];
num = min(num, board[i][y2]);
}
for(int i = y2; i > y1; i--) {
board[x1][i] = board[x1][i-1];
num = min(num, board[x1][i]);
}
board[x1][y1+1] = temp;
answer.push_back(num);
}
return answer;
}
단순하게 생각하면 N^N^2(true, false) 모든 경우의 수를 비교해서 찾을 수 있지만, N의 크기가 커질수록 연산량이
감당할 수 없는 수준으로 된다. 따라서 가지치기(Pruning)를 하면서 문제를 해결해야 한다.
가치지기란?
어떤 강을 건너기 위해 돌다리를 두들겨보듯이 그 돌이 안전한지 안한지, 유망했는지 아닌지를 검사해서 유망하면 건너가고 아니라면 다시 돌아와서 다른 길을 선택하는 방법이다.
기존의 DFS처럼 주먹구구식으로 끝까지 가보는 것은 어떤 문제에서는 좋지만 이 문제에서는 연산량이 감당이 되지 않기 때문에 DFS처럼 탐색은 하지만 유망한 지 안 한 지를 검사해서 탐색의 범위를 좁혀가면서 문제를 해결한다.
N-Queen에서는 가지치기는 내가 어떠한 행(row)에 0 ~ N 중 하나의 열(col)에 Queen을 둔다고 가정했을 때,
다음 행(row + 1)에 Queen을 두기 전에 내가 두었던 Queen이 기존 [0 ~ row-1]까지 Queen들과 서로 공격하지 않는 범위에 두었는지를 체크하는 방법이다.
위에 그림처럼
row = 2인 행에 0번째 열에 Queen을 배치했다고 생각하자.
그러면 지금 둔 Queen이 적절한 배치인지를 확인하기 위해서 0번째 행에 배치한 Queen, 1번째 행에 배치한 Queen과의 충돌이 일어나지 않는지를 체크하면 된다.
체크할 때는 같은 행에 있는지 체크는 배제하면 된다. 이유는 해당 행에는 한 개의 Queen만 배치하기 때문이다.
체크하는 코드를 보자. 우리가 유망한지 체크하는 방법은 같은 열에 걸리거나 대각선에 걸리면 그것은 유망하지 않다.
이럴 경우에는 다시 해당 row에 Queen을 배치하지 않고 다른 열에다가 배치하고 유망한 지를 검사해보고,
만약에 유망하다면 row + 1에 Queen을 배치하러 가면 된다.
int col[15]; // col[i] = j : (i,j)에 Queen을 배치
bool isPromising(int row)
{
// [0 ~ row) 단계 같은 열, 대각선 체크
for (int i = 0; i < row; i++)
{
if (col[i] == col[row]) return false;
if (abs(i - row) == abs(col[i] - col[row])) return false;
}
return true;
}
그렇다면 언제까지 Queen을 탐색할까?
row가 N까지 Queen을 잘 배치했다면, N x N 체스판 위에 N개의 Queen을 서로 공격할 수 없게 배치한 것이므로 이것은 문제에서 구하는 정답의 경우의 수 중 하나이기 때문에 개수를 하나 카운트하면 된다.
즉, row가 N이면 정답을 +1 증가시켜준다.
// row행 까지는 퀸을 놓은 상태,
void dfs(int row)
{
if (row == n)
{
ans++;
return;
}
// row행에 퀸을 배치하고 유망한지 체크
// 유망하다면 다음 행에 퀸을 배치하러 가고,
// 유망하지 않다면 다음 열에 다시 퀸을 배치하고 유망한지 검사한다.
for (int i = 0; i < n; i++)
{
col[row] = i;
if (isPromising(row))
dfs(row + 1);
}
}
정리하면,
각 단계(행)에서 어떤 열에 Queen을 둘지 정하고, Queen을 배치했다면 이전 단계에서 배치했던 모든 Queen들과 서로 공격하지 않는지를 검사해서 유망하다면 다음 단계로 넘어가고, 아니라면 그 단계에서 다음 열에 다시 Queen을 배치하는 방식으로 진행한다. 이렇게 하면 기존 DFS 탐색보다 빠르게 유망한 지 안 한 지 가지치기를 통해 더 빠르게 답을 구할 수 있을뿐더러 끝까지 탐색하지 않아도 된다는 장점이 있다.
전체 소스코드는 다음과 같다.
#include <iostream>
#include <cmath>
using namespace std;
int n, ans;
int col[15]; // col[i] = j : (i,j)에 Queen을 배치
bool isPromising(int row)
{
// [0 ~ row) 단계 같은 열, 대각선 체크
for (int i = 0; i < row; i++)
{
if (col[i] == col[row]) return false;
if (abs(i - row) == abs(col[i] - col[row])) return false;
}
return true;
}
// row행 까지는 퀸을 놓은 상태,
void dfs(int row)
{
if (row == n)
{
ans++;
return;
}
// row행에 퀸을 배치하고 유망한지 체크
// 유망하다면 다음 행에 퀸을 배치하러 가고,
// 유망하지 않다면 다음 열에 다시 퀸을 배치하고 유망한지 검사한다.
for (int i = 0; i < n; i++)
{
col[row] = i;
if (isPromising(row))
dfs(row + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
dfs(0);
cout << ans << '\n';
return 0;
}
int start = 0; // 문제마다 start와 end 값은 변동될 수 있다.
int end = 1e8; // 범위가 커진다면 long long 자료형으로 오버플로우를 방지할 수 있다.
int ans = 0;
while(start <= end)
{
int mid = (start + end) / 2;
if(calc(mid)) // 조건을 만족한다면
{
ans = mid;
s = mid + 1; // 한 걸음 더 가보자.
}
else
e = mid - 1; // 조건을 만족하지 못하니까, 탐색 범위를 줄여보자.
}
또, 파라메트릭 서치 같은 문제들은 범위가 어마어마하게 크다. 보통 O(N)으로 해결될 수 없는 문제들 같은 경우 이러한 방법도 생각해보는 것도 좋다.
