(단계 2). 검사 도중 숫자 x가 위의 세 조건을 모두 만족한다면 다음 빈칸으로 이동 후 (단계 1)진행
(단계 3). 현재 빈칸에서 어떤 숫자도 만족 할 수 없다면 전 빈칸으로 이동 후 x+1~9에 대해 (단계 1)진행
(단계 4). 완성된 스도쿠 출력 후 종료
소스 코드
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
vector<pair<int, int>> blank;
int sudoku[9][9] = {0};
void make_sudoku() {
int num;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> num;
sudoku[i][j] = num;
if (num == 0)
blank.push_back(make_pair(i, j));
}
}
}
int check1(int num, int row) { //행 지정
for (int i = 0; i < 9; i++) {
if (sudoku[row][i] == num) { //열 검사
return 0;
}
}
return 1;
}
int check2(int num, int col) { //열 지정
for (int i = 0; i < 9; i++) {
if (sudoku[i][col] == num) { //열 검사
return 0;
}
}
return 1;
}
int check3(int num, int row, int col) { // 행,열
int x = row / 3;
int y = col / 3;
x = x * 3;
y = y * 3;
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
if (sudoku[i][j] == num) { // 3X3박스 검사
return 0;
}
}
}
return 1;
}
void solve_sudoku(int cnt) {
if (cnt == blank.size()) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << sudoku[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
else {
for (int i = 1; i <= 9; i++) { //빈칸을 채워넣을 숫자
int x = blank[cnt].first;
int y = blank[cnt].second;
if (check1(i, x) * check2(i, y) * check3(i, x, y) == 1) { //조건을 모두 만족할때
sudoku[x][y] = i;
solve_sudoku(cnt + 1);
sudoku[x][y] = 0;
}
}
}
}
int main() {
make_sudoku();
solve_sudoku(0);
}
문제에서 요구하는 것을 간단히 정리하자면, A라는 인물과 B라는 인물이 친구 관계를 맺었을 때 A의 친구 수와 B의 친구 수를 더하면 된다. 문제를 읽었을 때 두 집합이 연결(친구 관계) 또는 합(친구의 수)하여 진다는 점에 있어서 유니온 파인드 알고리즘이라는 느낌이 확실히 와 닿는다.
유니온 파인드는 크게 자신의 루트를 찾는 find함수와, 두 집한간의 연결을 하는 Union함수를 사용한다.
혹여나 두 함수를 이해하지 못했다면 기본적인 UnionFind 알고리즘을 다시 공부하고 풀어보자.
사실 UnionFind의 구현은 어렵지 않으나, 이 문제는 노드 번호를 이름(문자열)으로 주어지기 때문에 조금 까다롭게 느껴질 수 있다.
1. 문자열을 노드 번호로 정리해 보자
map <string, int> name;
name을 map의 자료형으로 위와 같이 정의했을 때, 아래와 같이 처리할 수 있다.
int idx = 1;
for (int j = 0; j < F; j++) {
string name1, name2;
cin >> name1 >> name2;
if (name.count(name1) == 0)
name[name1] = idx++;
if (name.count(name2) == 0)
name[name2] = idx++;
Union(name[name1], name[name2]);
}
문제를 쉽게 해결하기 위해 이름(문자열)에 대해 번호를 매겨주자.
지금까지 입력받은 적이 없는 이름이라면 ( if (name.count(name1)==0) ), 번호를 부여한다( name[name1] = idx++) .
즉 idx는 이름에 대한 번호이며, 입력을 받은적이 있는 이름이라면 이미 번호가 매겨져 있다는 뜻으로 무시해도 된다는 것이다.
예를 들면
Fred, Bob -> 1, 2
Jason, Bob -> 3, 2
이렇게 처리가 된다.
이제 어려울 것이 없다. 친구 수는 (cnt[i] = 친구수 (i는 노드 번호))라는 배열에 저장하며 처리를 할 것이며 Union함수에서 name1과 name2의 친구 관계를 형성함과 동시에 친구수를 더할 것이다.
void Union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) //이미 친구 관계라면, 친구 수를 합하면 안됨
cnt[a] += cnt[b]; //친구수의 합
tree[b] = a; //친구관계 형성
cout << cnt[a] << "\n";
}
소스 코드
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <stdio.h>
using namespace std;
int tree[100010];
int cnt[100010];
int find(int a) {
if (tree[a] == -1 || tree[a] == a)
return a;
int root = find(tree[a]);
return tree[a] = root;
}
void Union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) //친구 관계가 아닐 때
cnt[a] += cnt[b]; //친구 수 합
tree[b] = a; //관계를 형성
cout << cnt[a] << "\n";
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T , F;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> F;
map <string, int> name;
memset(tree, -1, sizeof(tree));
fill_n(cnt, 100010, 1);
int idx = 1;
for (int j = 0; j < F; j++) {
string name1, name2;
cin >> name1 >> name2;
if (name.count(name1) == 0)
name[name1] = idx++;
if (name.count(name2) == 0)
name[name2] = idx++;
Union(name[name1], name[name2]);
}
}
}
이 문제는 구역만 조건에 따라 잘 나눠 주면 된다. 구역에 대한 합을 구하며 방문여부를 체크하자.
구역 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;
}
