이 문제는 구역만 조건에 따라 잘 나눠 주면 된다. 구역에 대한 합을 구하며 방문여부를 체크하자.
구역 1: 빨간색
구역 2: 노란색
구역 3: 파란색
구역 4: 초록색
구역 5: 갈색 테두리를 포함한 흰색
n = 8, x = 2, y = 4, d1 = 2, d2 = 2 일때의 예시
(1) 구역 1
구역 1에 대한 범위는 문제에 주어졌듯이 1 ≤ i < x+d1, 1 ≤ j ≤ y 이다. 하지만 이 범위에서 그림에서 빨간 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 빨간색과 인접한 갈색부분을 보자. 그 갈색 부분의 합은 x+y=6으로 일정하다. 그러므로 모든 빨간부분은
i+j <x+y= 6이다.
int area1(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i < x + d1; i++)
for (int j = 1; j <= y; j++) {
if (i + j < x + y) {
visited[i][j] = 1;
sum += map[i][j];
}
}
return sum;
}
(2) 구역 2
구역 2에 대한 범위는 1 ≤ i ≤ x+d2, y < j ≤ N 이다. 하지만 이 범위에서 그림에서 노란 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 빨간색과 인접한 갈색부분을 보자. 그 갈색 부분의 차는 y - x = 2로 일정하다. 그러므로 모든 노란부분은 (y - x = 2) < j - i
이다.
int area2(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i <= x + d2; i++)
for (int j = y+1; j <= n; j++) {
if (y - x < j - i) {
visited[i][j] = 2;
sum += map[i][j];
}
}
return sum;
}
(3) 구역 3
구역 3에 대한 범위는x+d1≤ i ≤ N, 1 ≤ j < y-d1+d2이다. 하지만 이 범위에서 그림에서 파란 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 파란색과 인접한 갈색부분을 보자. 그 갈색 부분의 차는 x - y + 2 * d1 = 2로 일정하다.
그러므로 모든 파란부분은 (y - x + 2 * d1 = 2) < i - j 이다.
int area3(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = x + d1; i <= n; i++)
for (int j = 1; j < y - d1 + d2; j++)
if (x - y + 2 * d1 < i - j) {
visited[i][j] = 3;
sum += map[i][j];
}
return sum;
}
(4) 구역 4
구역 4에 대한 범위는x+d2< i ≤ N, y-d1+d2 ≤ j ≤ N이다. 하지만 이 범위에서 그림에서 초록 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 초록색과 인접한 갈색부분을 보자. 그 갈색 부분의 합은 x + y + 2 * d2 = 10으로 일정하다.
그러므로 모든 파란부분은 (x + y + 2 * d2 = 10) < i + j이다.
int area4(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = x + d2 + 1; i <= n; i++)
for (int j = y - d1 + d2; j <= n; j++)
if (i + j > x + y + 2 * d2) {
visited[i][j] = 4;
sum += map[i][j];
}
return sum;
}
(5) 구역 5
구역 1,2,3,4를 제외한 모든 부분이다.
소스 코드
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int map[21][21];
int visited[21][21];
int n;
int area1(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i < x + d1; i++)
for (int j = 1; j <= y; j++) {
if (i + j < x + y) {
visited[i][j] = 1;
sum += map[i][j];
}
}
return sum;
}
int area2(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i <= x + d2; i++)
for (int j = y+1; j <= n; j++) {
if (y - x < j - i) {
visited[i][j] = 2;
sum += map[i][j];
}
}
return sum;
}
int area3(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = x + d1; i <= n; i++) {
for (int j = 1; j < y - d1 + d2; j++) {
if (x - y + 2 * d1 < i - j) {
visited[i][j] = 3;
sum += map[i][j];
}
}
}
return sum;
}
int area4(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = x + d2 + 1; i <= n; i++) {
for (int j = y - d1 + d2; j <= n; j++) {
if (i + j > x + y + 2 * d2) {
visited[i][j] = 4;
sum += map[i][j];
}
}
}
return sum;
}
int area5(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (visited[i][j] == 0) {
visited[i][j] = 5;
sum += map[i][j];
}
return sum;
}
int make_area(int x, int y, int d1, int d2) {
int cnt1 = area1(x, y, d1, d2);
int cnt2 = area2(x, y, d1, d2);
int cnt3 = area3(x, y, d1, d2);
int cnt4 = area4(x, y, d1, d2);
int cnt5 = area5(x, y, d1, d2);
int maxi = max(cnt1, max(cnt2, max(cnt3, max(cnt4, cnt5))));
int mini = min(cnt1, min(cnt2, min(cnt3, min(cnt4, cnt5))));
return maxi - mini;
}
int solve(){
int result = 0xFFFFFFF;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
for (int d1 = 1; d1 <= n; d1++)
for (int d2 = 1; d2 <= n; d2++)
if (1 <= x && x + d1 + d2 <= n && 1 <= y - d1 && y + d2 <= n) {
memset(visited, 0, sizeof(visited));
result = min(result, make_area(x, y, d1, d2));
}
return result;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> map[i][j];
cout << solve() << endl;
}
typedef struct horse {
int y;
int x;
int d;
};
horse h[MAXK];
int N, K, map[MAX][MAX];
vector<int> section[MAX][MAX];
const pair<int, int> direction[5] = { {0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
위와 같은 구조의 변수를 정의하여 사용하였다.
section[][]에는 말이 stack된 것을 vector로 표현하였다.
이 문제를 풀면서 가장 오래걸렸던 부분은 다음 영역으로 이동할 때, 다음 영역에 존재하는 다른 말보다 위에 쌓아야 하는 조건을 반대로 해석해서 시간을 잡아먹은 것과, 말이 벽이나 파란색 영역을 만났을 때, 뒤집어서 다시 전진하는 부분이었다.
이 문제는 특별한 알고리즘이 있는 문제가 아니라서 설명은 생략하겠다. 코드를 참고 바란다.
소스 코드
#include <vector>
#include <iostream>
#include <algorithm>
#define MAX 13
#define MAXK 11
using namespace std;
typedef struct horse {
int y;
int x;
int d;
};
horse h[MAXK];
int N, K, map[MAX][MAX];
vector<int> section[MAX][MAX];
const pair<int, int> direction[5] = { {0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
void update_coord(vector<int>& upper, int ny, int nx) {
for (int i = 0; i < upper.size(); ++i) {
h[upper[i]].y = ny;
h[upper[i]].x = nx;
}
}
// k번째 말을 움직인다.
bool move(int ny, int nx, int k) {
vector<int>& from = section[h[k].y][h[k].x];
vector<int>& to = section[ny][nx];
vector<int> upper;
for (int i = 0; i < from.size(); ++i) {
if (from[i] == k) {
upper.assign(from.begin() + i, from.end());
from.assign(from.begin(), from.begin() + i);
}
}
update_coord(upper, ny, nx);
if (map[ny][nx] == 0) { // 흰색
if (to.empty()) // 다음칸이 비어있다면
to = upper; // 그냥 이동
else { // 다음 칸에 말이 이미 있는 경우
for (int i = 0; i < upper.size(); ++i) {
to.push_back(upper[i]);
}
}
}
else if (map[ny][nx] == 1) { // 빨간색
reverse(upper.begin(), upper.end()); // 일단 뒤집는다.
if (to.empty()) // 다음칸이 비어있다면
to = upper; // 그냥 이동
else { // 다음 칸에 말이 이미 있는 경우
for (int i = 0; i < upper.size(); ++i) {
to.push_back(upper[i]);
}
}
}
if (to.size() >= 4) return true;
else return false;
}
bool is_movable(int ny, int nx) {
if (ny > N || nx > N || ny < 1 || nx < 1 || map[ny][nx] == 2) return false;
return true;
}
void update_direct(int k) {
int opposite_d = 0;
if (h[k].d == 1) opposite_d = 2;
else if (h[k].d == 2) opposite_d = 1;
else if (h[k].d == 3) opposite_d = 4;
else if (h[k].d == 4) opposite_d = 3;
h[k].d = opposite_d;
}
bool turn_back(int y, int x, int k) {
int i;
vector<int>& from = section[y][x];
vector<int> upper;
for (i = 0; i < from.size(); ++i) {
if (k == from[i]) {
upper.assign(from.begin() + i, from.end());
}
}
update_direct(k);
int ny = y + direction[h[k].d].first;
int nx = x + direction[h[k].d].second;
if (!is_movable(ny, nx)) return false;
return move(ny, nx, k);
}
bool turn() {
for (int k = 1; k <= K; ++k) {
int ny = h[k].y + direction[h[k].d].first;
int nx = h[k].x + direction[h[k].d].second;
if (!is_movable(ny, nx)) {
if (turn_back(h[k].y, h[k].x, k)) return true;
}
else {
if (move(ny, nx, k)) return true;
}
}
return false;
}
int solve() {
int ret = 0;
while (ret < 1000) {
++ret;
if (turn()) break;
}
if (ret >= 1000) return -1;
else return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
cin >> map[i][j];
for (int i = 1; i <= K; ++i) {
cin >> h[i].y >> h[i].x >> h[i].d;
section[h[i].y][h[i].x].push_back(i);
}
cout << solve();
return 0;
}
이 문제는 내리막 길(현재보다 더 값이 작은 지점)으로만 따라 갔을 때, 목적지에 도착하는 길의 수를 구하는 문제이며, 문제를 보았을때 DFS를 사용하면 top-down방식으로 가능할 것이고, BFS를 사용하면 bottom-up방식이 가능하다. 필자는 DFS를 이용한 top-down방식으로 해결하였다.
(1) 변수
dp[i][j]는 i,j에서 출발하였을 때, 내리막 길을 따라 도착지에 도착하였을 경우에 대한 길의 수이며, 방문 여부로도 사용된다. 초기값을 0으로 사용하게 되면, 방문을 하였어도 도착지점까지 못 간다면 계속 0이기 때문에 방문여부를 확인하기 어렵기 때문에 초기값을 -1로 하였다.
(2) solve()
int &ret = dp[x][y];
if (ret != -1) return ret;
if (x == n && y == m) return ret = 1;
ret = 0;
함수가 호출되었을때, 가장 먼저 방문여부( if (ret != -1) )를 판단한다. 중복되는 연산을 피하기 위해서이다. 방문을 하였으면 해당 dp에 저장된 값을 return한다. 좀 더 자세히 설명을 하자면 어차피 현재 함수의 x,y에서 갈 수 있는 경로를 이미 다 탐색을 한 값이 dp[x][y]에 저장되어 있으므로 함수를 더 진행시킬 필요가 없다는 것이다.
그 다음 도착지점에 도착했다면( if (x == n && y == m) ), 도착한 경로에 대한 경우가 추가 되었으므로 1을 return한다.
위의 두가지 경우가 아니면 방문을 했다는 의미로 값을 0으로 바꿔준다.
for (int i = 0; i < 4; i++) {
int next_x = x + direction[i].first;
int next_y = y + direction[i].second;
if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m)
if (map[next_x][next_y] < map[x][y])
ret += solve(next_x, next_y);
}
그 이후 현재좌표의 상하좌우 4방향에 대해 map에 포함되어 있는 범위 내에서, 값이 더 작은 곳으로 이동시키면 된다.
소스 코드
#include <iostream>
#include <string.h>
using namespace std;
int n, m;
int map[501][501];
int dp[501][501];
pair<int, int> direction[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int solve(int x, int y) {
int &ret = dp[x][y];
if (ret != -1) return ret;
if (x == n && y == m) return ret = 1;
ret = 0;
for (int i = 0; i < 4; i++) {
int next_x = x + direction[i].first;
int next_y = y + direction[i].second;
if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m)
if (map[next_x][next_y] < map[x][y])
ret += solve(next_x, next_y);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
memset(dp, -1, sizeof(dp));
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
cout << solve(1, 1);
}
모든 면에 대한 색상을 큐브를 돌릴 때 마다 일일히 바꿔주는 것은 고려해야할 것이 너무 많다고 생각했습니다. 제가 접근한 방법은 3x3x3의 큐브의 각 단위에 해당하는 '작은 큐브'를 정의하는 것이었습니다. '작은 큐브'는 쉽게 말해서 정육면체이며, 6가지 면에 대한 색상 정보를 담습니다.
void init_cuve() {
for (int h = 0; h < 3; ++h) {
for (int y = 0; y < 3; ++y) {
for (int x = 0; x < 3; ++x) {
cuv[h][y][x].top = 'w';
cuv[h][y][x].bot = 'y';
cuv[h][y][x].front = 'r';
cuv[h][y][x].back = 'o';
cuv[h][y][x].left = 'g';
cuv[h][y][x].right = 'b';
}
}
}
}
각 작은 큐브는 표면에 노출된 면만 고정적으로 노출되므로 보이지 않는 면을 초기화 한다해도 문제 없습니다.
이제 큐브 정의가 끝났습니다. 이제 면(side)과 방향(direction)을 입력받아서 큐브를 회전하는 함수를 짜봅시다.
회전의 정의는 큐브의 회전은 '각 면을 정면에서 바라보았을 때의 시계/반시계 방향'으로 이루어진다고 나와있습니다.
그 말을 각 면에 대해서 그림을 그려본다면, 앞(F)면을 시계방향으로 회전하는 것과, 뒷(B)면을 반시계방향으로 회전하는 것의 방향이 같음을 알 수 있습니다. 또한 (h, y, x)의 좌표계에서 바라보면 앞면과 뒷면은 h좌표가 고정이고, (x, y)좌표만 움직임을 알 수 있습니다. 이를 정리하면 아래와 같습니다.
BFS 알고리즘의 문제인데, 신경써야할 대상이 2개 (빨간 공, 파란 공)라서 매우 까다롭습니다.
먼저 코딩부터 시작하면 중간에 흐름을 놓치기 쉽습니다. 단계적으로 천천히 접근해보도록 하겠습니다.
1) 데이터 형태 정의
typedef struct ball {
int y, x;
};
typedef struct balls {
ball red;
ball blue;
int count;
};
ball 구조체는 빨간 공, 파란 공을 나타낼 구조체입니다.
balls 구조체는 BFS 탐색을 위해서 큐에 빨간 공과 파란 공을 묶어서 담기 위한 구조체이며, count는 판을 기울인 횟수를 기록합니다.
2) 데이터 입력받기
ball red, blue;
char map[MAX][MAX];
void input() {
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> map[i][j];
if (map[i][j] == 'R') { // 빨간공에 대한 정보 담기
red = { i, j };
map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
}
else if (map[i][j] == 'B') { // 파란공에 대한 정보 담기
blue = { i, j };
map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
}
}
}
}
char형으로 map에 데이터를 입력해줍니다. red와 blue는 좌표로 다룰 것이므로, map에 'R'과 'B'는 지워줍니다.
3) 공의 이동을 함수로 구현하기
const pair<int, int> direction[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
bool isMovable(int y, int x, int other_y, int other_x) {
if (map[y][x] == '#') return false;
if (y == other_y && x == other_x) { // 다른 공과 좌표가 같은 경우
if (map[y][x] == 'O') return true; // 목적지인 경우에는 겹치기 허용
else return false; // 목적지가 아니면 공끼리 겹치기 허용하지 않음
}
return true; // 벽, 공 겹치는 경우 외에는 이동 가능
}
ball move(ball obj, ball other, int d) {
int ny, nx;
while (1) {
ny = obj.y + direction[d].first;
nx = obj.x + direction[d].second;
if (!isMovable(ny, nx, other.y, other.x)) break;
if (map[ny][nx] == 'O') { // 목적지인 경우에는 이동하고 종료
obj.y = ny; obj.x = nx;
break;
}
obj.y = ny; obj.x = nx; // 이상 없으면 해당 좌표로 이동
}
return obj;
}
direction[4] = {오른쪽, 아래, 왼쪽, 위}로 정의를 해준 뒤, 공 1개를 방향 d로 움직이는 함수를 구현합니다. isMovable 함수를 통해서 공이 움직일 수 있는 경우와 움직일 수 없는 경우를 꼼꼼히 구분해줍니다. move함수를 통하여 공 1개의 움직임을 다른 공과 겹치지 않게 방향 d로 움직여줍니다. 판이 기울었기 때문에 공은 어떤 다른 오브젝트에 부딪혀서 움직이지 못할때까지 이동할 것입니다.
4) 판을 기울이는 함수 구현하기
// 주어진 조건에 판을 기울여서 공을 움직인 뒤, 공의 이동한 좌표를 반환하는 함수
// 공의 좌표가 겹치는 경우는 오직 목적지에 도착했을 경우이다.
balls tilt(balls current, int direct) {
balls next = current;
if (direct == 0) { // 우측으로 기울이는 경우 (x++)
if (current.red.x > current.blue.x) { // x가 더 큰 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 우측에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
else if (direct == 1) { // 아래로 기울이는 경우 (y++)
if (current.red.y > current.blue.y) { // y가 더 큰 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 하단에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
else if (direct == 2) { // 좌측으로 기울이는 경우 (x--)
if (current.red.x < current.blue.x) { // x가 더 작은 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
else if (direct == 3) { // 상단으로 기울이는 경우 (y--)
if (current.red.y < current.blue.y) { // y가 더 작은 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
return next; // 이동한 좌표를 반환한다.
}
판이 기울어졌을때 먼저 고려해야할 것은 '어떤 공을 먼저 움직일 것인가?' 입니다. 저는 방향별로 기울여진 방향쪽에 더 가까운 공을 먼저 움직이는 방법을 택하였습니다. 빨간 공과 파란 공의 현재 위치 정보가 담긴 balls current를 입력 받아서, 주어진 방향 direct로 이동한 좌표 balls next를 반환합니다.
5) BFS 구현
int bfs() {
queue<balls> q;
q.push({ red, blue, 1 });
visit[red.y][red.x][blue.y][blue.x] = 1;
bool break_flag = false;
int level_size, ret = INF;
balls current, next;
while (!q.empty()) {
level_size = q.size();
while (level_size--) {
current = q.front(); q.pop();
if (current.count > 10) {
break_flag = true;
break;
}
for (int direct = 0; direct < 4; ++direct) {
next = tilt(current, direct);
if (map[next.red.y][next.red.x] == 'O') { // red가 빠져나갔다면
if (map[next.blue.y][next.blue.x] == 'O') { // blue도 빠져나갔다면
visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
continue; // 다른 방향으로 기울여본다.
}
else { // red만 빠져나갔다면
ret = min(ret, current.count); // 최소값 갱신
}
}
else if (map[next.blue.y][next.blue.x] == 'O') { // blue만 빠져나갔다면
visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
continue; // 다른 방향으로 기울여본다.
}
else if (!visit[next.red.y][next.red.x][next.blue.y][next.blue.x]) {
++next.count;
q.push(next);
visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
}
}
}
if (break_flag) break;
}
if (ret == INF) return -1;
else return ret;
}
BFS를 구현할 때 가장 중요하다고 생각이 들었던 것은, visit를 4차원으로 표현하는 것이었습니다. 판이 기울여지면 공은 기울여진 방향 d로 끝까지 이동하고, 빨간 공, 파란 공 둘의 위치를 모두 고려해야 하므로 4차원으로 사용하였습니다.
저는 빨간 공과 파란 공을 목적지에 도달한 경우에만 겹치게 하였기 때문에, 둘 다 겹치는 경우, 한 가지만 겹치는 경우로 나누어서 결과를 구분할 수 있었습니다.
전체 소스 코드
#include <queue>
#include <iostream>
#include <algorithm>
#define MAX 10
using namespace std;
typedef struct ball {
int y, x;
};
typedef struct balls {
ball red;
ball blue;
int count;
};
ball red, blue;
char map[MAX][MAX];
const int INF = 99999999;
int N, M, visit[MAX][MAX][MAX][MAX];
const pair<int, int> direction[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
void input() {
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> map[i][j];
if (map[i][j] == 'R') { // 빨간공에 대한 정보 담기
red = { i, j };
map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
}
else if (map[i][j] == 'B') { // 파란공에 대한 정보 담기
blue = { i, j };
map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
}
}
}
}
bool isMovable(int y, int x, int other_y, int other_x) {
if (map[y][x] == '#') return false;
if (y == other_y && x == other_x) { // 다른 공과 좌표가 같은 경우
if (map[y][x] == 'O') return true; // 목적지인 경우에는 겹치기 허용
else return false; // 목적지가 아니면 공끼리 겹치기 허용하지 않음
}
return true; // 벽, 공 겹치는 경우 외에는 이동 가능
}
ball move(ball obj, ball other, int d) {
int ny, nx;
while (1) {
ny = obj.y + direction[d].first;
nx = obj.x + direction[d].second;
if (!isMovable(ny, nx, other.y, other.x)) break;
if (map[ny][nx] == 'O') { // 목적지인 경우에는 이동하고 종료
obj.y = ny; obj.x = nx;
break;
}
obj.y = ny; obj.x = nx; // 이상 없으면 해당 좌표로 이동
}
return obj;
}
// 주어진 조건에 판을 기울여서 공을 움직인 뒤, 공의 이동한 좌표를 반환하는 함수
// 공의 좌표가 겹치는 경우는 오직 목적지에 도착했을 경우이다.
balls tilt(balls current, int direct) {
balls next = current;
if (direct == 0) { // 우측으로 기울이는 경우 (x++)
if (current.red.x > current.blue.x) { // x가 더 큰 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 우측에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
else if (direct == 1) { // 아래로 기울이는 경우 (y++)
if (current.red.y > current.blue.y) { // y가 더 큰 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 하단에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
else if (direct == 2) { // 좌측으로 기울이는 경우 (x--)
if (current.red.x < current.blue.x) { // x가 더 작은 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
else if (direct == 3) { // 상단으로 기울이는 경우 (y--)
if (current.red.y < current.blue.y) { // y가 더 작은 쪽이 먼저 움직여야 한다.
next.red = move(current.red, current.blue, direct);
next.blue = move(current.blue, next.red, direct);
}
else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
next.blue = move(current.blue, current.red, direct);
next.red = move(current.red, next.blue, direct);
}
}
return next; // 이동한 좌표를 반환한다.
}
int bfs() {
queue<balls> q;
q.push({ red, blue, 1 });
visit[red.y][red.x][blue.y][blue.x] = 1;
bool break_flag = false;
int level_size, ret = INF;
balls current, next;
while (!q.empty()) {
level_size = q.size();
while (level_size--) {
current = q.front(); q.pop();
if (current.count > 10) {
break_flag = true;
break;
}
for (int direct = 0; direct < 4; ++direct) {
next = tilt(current, direct);
if (map[next.red.y][next.red.x] == 'O') { // red가 빠져나갔다면
if (map[next.blue.y][next.blue.x] == 'O') { // blue도 빠져나갔다면
visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
continue; // 다른 방향으로 기울여본다.
}
else { // red만 빠져나갔다면
ret = min(ret, current.count); // 최소값 갱신
}
}
else if (map[next.blue.y][next.blue.x] == 'O') { // blue만 빠져나갔다면
visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
continue; // 다른 방향으로 기울여본다.
}
else if (!visit[next.red.y][next.red.x][next.blue.y][next.blue.x]) {
++next.count;
q.push(next);
visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
}
}
}
if (break_flag) break;
}
if (ret == INF) return -1;
else return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
cout << bfs();
return 0;
}
이 문제는 사다리에 추가적으로 가로선을 0개 부터 최대 3개까지 놓는 가능한 모든 경우의 수를 다 보아야 해결 할 수 있다. 결국 조합 문제로 해석될 수 있으므로, 백트래킹을 하며 모든 조합에 대해 문제의 조건은 1번째부터 i번째에서 출발할 때 순서대로 1번째부터 i번째의 도착 지점에 도달하면 카운트하고, 그 카운트가 4이상이거나 가능한 방법이 없다면 -1을 출력하면 된다.
(1) 변수
map[h][l]는 h의 높이, l번째 라인이 h의 높이, l+1번째 라인에 가로선이 연결되어 있다면 1, 아니면 0으로 나타낸다.
(2) go() 함수
bool go() {
for (int i = 1; i <= N; i++) {
int nowl = i;
for (int nowh = 0; nowh <= H; nowh++){
if (map[nowh][nowl] == 1)
nowl++;
else if (map[nowh][nowl - 1] == 1)
nowl--;
}
if (nowl != i)
return false;
}
return true;
}
이 함수는 사다리의 출발지점과 도착지점이 같은지 따라가보는 함수이다.
모든 사다리의 출발지점 1~N에 대해 확인 하여야 하기 때문에 for문에서 경우를 검사해보자. 현재 출발 라인을 nowl = i 라 하고, nowh(0~H)를 따라갈때, 우측에 사다리가 있는 경우 (if(map[nowh][nowl] == 1)) 라인을 오른쪽으로 옮겨갈 것(nowl++)이고, 좌측에 사다리가 있는 경우(if(map[nowh][nowl - 1] == 1)) 라인을 왼쪽으로 옮겨갈 것(nowl--)이다.
(3) solve()함수
void solve(int cnt, int now_h, int now_l) {
if (go()) {
result = min(cnt, result);
return;
}
if (cnt == 3)
return;
for (int h = now_h; h <= H; h++) {
for (int l = now_l; l < N; l++) {
if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
map[h][l] = 1;
solve(cnt + 1, h, l);
map[h][l] = 0;
}
}
now_l = 1;
}
}
이 함수는 조합을 보기 위한 백트래킹(DFS) 함수이다. 중복되는 경우를 보지 않기 위해 매게변수로(nowl, nowh)를 사용하였으며, 위 함수가 호출되는 모든 경우에 대해 위에 설명한 go()함수로 조건을 만족하는지 검사한다. cnt가 3보다 커지는 경우는 고려하지 않으므로 cnt는 3에서 return을 하게 된다.
가로선을 추가 할 수 있는 경우인,
양쪽에 가로라인이 존재하지 않을 때(if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0))
가로라인을 추가(map[h][l] = 1)하고, 함수를 진행 시킨뒤(solve(cnt + 1, h, 1)), 함수가 종료되면 해당 가로라인을 다시 삭제 (map[h][l] = 0)하면 된다.
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, H;
int map[32][12]; //height, line
int result = 4;
bool go() {
for (int i = 1; i <= N; i++) {
int nowl = i;
for (int nowh = 0; nowh <= H; nowh++){
if (map[nowh][nowl] == 1)
nowl++;
else if (map[nowh][nowl - 1] == 1)
nowl--;
}
if (nowl != i)
return false;
}
return true;
}
void solve(int cnt, int now_h, int now_l) {
if (go()) {
result = min(cnt, result);
return;
}
if (cnt == 3)
return;
for (int h = now_h; h <= H; h++) {
for (int l = now_l; l < N; l++) {
if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
map[h][l] = 1;
solve(cnt + 1, h, l);
map[h][l] = 0;
}
}
now_l = 1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> H;
for (int i = 1; i <= M; i++) {
int a, b;
cin >> a >> b; //a높이 b라인
map[a][b] = 1;
}
solve(0, 1, 1);
if (result >= 4)
cout << -1 << "\n";
else
cout << result << "\n";
}
주어지는 톱니 바퀴는 반시계방향, 시계방향으로 회전할 수 있으며, 옆에 다른 톱니바퀴의 회전에 영향을 줄 수 있다. 위의 톱니 바퀴를 수로 표현하면 10101111입니다. 각 숫자를 원형큐로 구현하여 회전을 쉽게 구현할 수 있습니다. 저는 원형큐가 익숙하지 않아서 보이는 그대로 비트 연산을 통해 구현하였습니다. 따라서 비트 연산으로 설명을 할 것인데, 리스트로 구현한 코드도 같이 올리도록 하겠습니다.
양 옆의 톱니 바퀴의 회전을 고려하기 전에, 기본 회전 코드를 먼저 짜는게 좋습니다.
<시계 방향 회전>
10101111 -> 01010111 (>> 연산만 한 결과 temp_bit = 1) -> 11010111 (temp_bit을 2^7로 올린 결과)
temp_bit = 1
>> 연산과 2^0 자릿수의 1을 다시 2^7으로 올리는 코드 구현
if (direct == 1) { // 시계 방향(오른쪽으로, 7번째 비트 저장 필요)
temp_bit = get_bit(g, 7) << 7;
gear = gear >> 1;
gear |= temp_bit;
}
<반시계 방향 회전>
10101111 -> 01011110 (<< 연산만 한 결과, temp_bit = 1) -> 01011111 (temp_bit을 2^0으로 올린 결과)
<< 연산과 2^7 자릿수를 다시 2^0으로 내리는 코드 구현
else if (direct == -1) { // 반시계 방향(왼쪽으로, 0번째 비트 저장 필요)
temp_bit = get_bit(g, 0);
gear = gear << 1;
gear |= temp_bit;
}
여기서 get_bit(g, idx)는 g라는 2진수 값에서 idx번째 자릿수를 얻는 연산입니다. 코드는 아래와 같습니다.
int get_bit(int g, int idx) {
int temp = 1 << (7 - idx);
int gear_bit = (gears[g] & temp);
while (gear_bit > 1) {
gear_bit = gear_bit >> 1;
}
return gear_bit;
}
자, 이제 g번째 바퀴를 회전시킬 때, 맞닿은 톱니 바퀴의 값이 반대인 경우, 해당 바퀴도 반대 방향으로 회전해주는 코드를 작성해볼게요.
i번 바퀴로 설명하겠습니다.
1. (i - 1)번 바퀴의 2번 비트가 (i)번 바퀴의 6번 비트와 다르다면 회전
2. (i + 1)번 바퀴의 6번 비트가 (i)번 바퀴의 2번 비트와 다르다면 회전
이 두 가지 조건에 visit 배열을 통한 바퀴 방문 여부, (i - 1), (i + 1) 인덱스 참조가 가능한지의 조건만 더해지면 재귀 함수를 완성할 수 있습니다. 설명과 아래 코드를 비교해보세요.
// g번째 바퀴의 g_idx와 ng번째 바퀴의 ng_idx가 같으면 true, 아니면 false
bool is_samebit(int g, int g_idx, int ng, int ng_idx) {
return get_bit(g, g_idx) == get_bit(ng, ng_idx);
}
int rotate_gear(int g, int d) {
visit[g] = 1;
int rotated_gear = rotate(g, d);
// 왼쪽 기어 확인
if ((g - 1) >= 0 && !visit[g - 1] && !is_samebit(g, 6, g - 1, 2))
rotate_gear(g - 1, d * -1);
if ((g + 1) < NUM_GEARS && !visit[g + 1] && !is_samebit(g, 2, g + 1, 6))
rotate_gear(g + 1, d * -1);
gears[g] = rotated_gear;
return 0;
}
중요한 점은 회전을 먼저 하고 검사를 하면 안된다는 것입니다. 회전하기 전에 각 맞닿은 비트를 검사해놓고, 회전은 나중에 해야합니다. 문제를 잘 읽어보시면 이해가 가실겁니다.
비트 연산이 햇갈리시면 #include <bitset>을 하셔서 bitset<8>(gears[0])를 이용해서 직접 비트를 출력해보시면 도움이 많이 됩니다.
소스 코드
<비트로 구현>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>
#define NUM_GEARS 4
using namespace std;
int gears[NUM_GEARS], K, visit[NUM_GEARS];
int get_bit(int g, int idx) {
int temp = 1 << (7 - idx);
int gear_bit = (gears[g] & temp);
while (gear_bit > 1) {
gear_bit = gear_bit >> 1;
}
return gear_bit;
}
int rotate(int g, int direct) {
int temp_bit, gear = gears[g];
if (direct == 1) { // 시계 방향(오른쪽으로, 7번째 비트 저장 필요)
temp_bit = get_bit(g, 7) << 7;
gear = gear >> 1;
gear |= temp_bit;
}
else if (direct == -1) { // 반시계 방향(왼쪽으로, 0번째 비트 저장 필요)
temp_bit = get_bit(g, 0);
gear = gear << 1;
gear |= temp_bit;
}
return gear;
}
// g번째 바퀴의 g_idx와 ng번째 바퀴의 ng_idx가 같으면 true, 아니면 false
bool is_samebit(int g, int g_idx, int ng, int ng_idx) {
return get_bit(g, g_idx) == get_bit(ng, ng_idx);
}
int rotate_gear(int g, int d) {
visit[g] = 1;
int rotated_gear = rotate(g, d);
if ((g - 1) >= 0 && !visit[g - 1] && !is_samebit(g, 6, g - 1, 2))
rotate_gear(g - 1, d * -1); // 왼쪽 기어 확인
if ((g + 1) < NUM_GEARS && !visit[g + 1] && !is_samebit(g, 2, g + 1, 6))
rotate_gear(g + 1, d * -1); // 오른쪽 기어 확인
gears[g] = rotated_gear;
return 0;
}
int get_score() {
int ret = 0, bit, coefficient = 1;
for (int i = 0; i < NUM_GEARS; ++i) {
bit = get_bit(i, 0); // 0번째 비트 = 12시 방향의 비트
ret += coefficient * bit;
coefficient *= 2;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
char a;
for (int i = 0; i < NUM_GEARS; ++i) {
for (int j = 0; j < 8; ++j) {
cin >> a;
a -= '0';
gears[i] |= (a << (7 - j));
}
}
cin >> K;
int g, d;
for (int k = 0; k < K; ++k) {
memset(visit, 0, sizeof(visit));
cin >> g >> d;
rotate_gear(g - 1, d);
}
cout << get_score();
return 0;
}
<리스트로 구현>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define NUM_GEARS 4
using namespace std;
int gears[NUM_GEARS][8], K, visit[NUM_GEARS];
vector<pair<int, int>> ops;
// i번째 톱니바퀴를 d방향으로 회전
void rotate(int i, int d) {
int temp;
if (d == 1) { // 시계방향, 우측
temp = gears[i][7];
for (int j = 7; j >= 1; --j)
gears[i][j] = gears[i][j - 1];
gears[i][0] = temp;
}
else if (d == -1) { // 반시계방향, 좌측
temp = gears[i][0];
for (int j = 0; j + 1 < 8; ++j)
gears[i][j] = gears[i][j + 1];
gears[i][7] = temp;
}
}
// g번째 바퀴의 gi번째 비트와 ng번째 바퀴의 ngi번째 비트를 비교한다.
bool is_different(int g, int gi, int ng, int ngi) {
return gears[g][gi] != gears[ng][ngi]; // 같으면 true, 다르면 false
}
void check_rotate(int i, int d) {
visit[i] = 1;
ops.push_back({ i, d });
int left = i - 1, right = i + 1;
//cout << i << "번째 바퀴 => ";
if (left >= 0) { // 왼쪽이 존재한다면
//cout << "나의 6번째 값:" << gears[i][6] << " 왼쪽의 2번째 값:" << gears[i][2] << "\n";
if (!visit[left] && is_different(i, 6, left, 2)) {
check_rotate(left, d * -1);
}
}
if (right < NUM_GEARS) {
//cout << "나의 2번째 값:" << gears[i][2] << " 오른쪽의 6번째 값:" << gears[i][6] << "\n";
if (!visit[right] && is_different(i, 2, right, 6)) {
check_rotate(right, d * -1);
}
}
}
int get_score() {
int ret = 0, sum_check = 1;
for (int g = 0; g < NUM_GEARS; ++g) {
if (gears[g][0] == 1) ret += sum_check;
sum_check *= 2;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
char input;
for (int i = 0; i < NUM_GEARS; ++i)
for (int j = 0; j < 8; ++j) {
cin >> input;
gears[i][j] = input - '0';
}
cin >> K;
int g, d;
for (int k = 0; k < K; ++k) {
memset(visit, 0, sizeof(visit));
cin >> g >> d;
check_rotate(g - 1, d);
for (int i = 0; i < ops.size(); ++i) {
rotate(ops[i].first, ops[i].second);
}
ops.clear();
}
cout << get_score();
return 0;
}
