문제 정보
백준 ( BOJ ) 13460 구슬 탈출 2
문제 풀이 : DFS
문제 출처 : https://www.acmicpc.net/problem/13460
삼성 역량테스트 기출 문제
문제 풀이
dfs방식으로 한쪽 방향으로 모두 밀어 내는 방식으로 하면 됩니다.
다만 주의해야 할점은, 빨간공과 파란공 위치에 따라서 어느 공을 먼져 움직일지 선택을 해야 한다는 점입니다.
만약에 왼쪽으로 기울여서 공을 움직인다면, 더 왼쪽에 있는 공을 먼져 움직여 주시면 됩니다.
이렇게 해야 하는 이유는
골인 …… 빨간공 파란공
이상태에서 파란공을 먼져 움직인다면, 빨간공에 막혀 움직이지 않고, 그 후 빨간공만 골인하여
골인 …….. 파란공
이 상태가 되기 때문에, 올바른 결과를 얻을 수 없습니다.
-
각방향별로 한쪽으로 쭉 밈 (이때 방향 설정 )
-
민 후 다음 행동 취함
-
10번 넘어가면 정지
그리고, result 로 15를 설정 하고,
빨간공이 골인하면, 현재 몇번째인지를 result 에 저장합니다.
- 결과적으로 result 가 10 이하면, result를 출력하고, 아니면 -1 을 출력합니다.
문제 코드
#include <iostream>
#include <vector>
using namespace std;
int x = 0;
int y = 0;
int result = 15;
int tempx = 0;
int tempy = 0;
bool move(vector<vector<char>> &board, int direction, int rx, int ry, char simbol) {
int movex[4] = { -1,1,0,0 };
int movey[4] = { 0,0,-1,1 };
while ( board[ry + movey[direction]][rx + movex[direction]] == '.') {
board[ry + movey[direction]][rx + movex[direction]] = simbol;
board[ry][rx] = '.';
rx += movex[direction];
ry += movey[direction];
}
tempx = rx;
tempy = ry;
//print(board);
if (board[ry +movey[direction]][rx +movex[direction]] == 'O') {
board[ry][rx] = '.';
return true;
}
return false;
}
void bfs(vector<vector<char>> &board, int time,int rx, int ry, int bx, int by) {
bool r, b;
int trX, trY, tbX, tbY;
if (time <= 10) {
// to left
vector<vector<char>> copy = board;
r = false;
b = false;
if (rx < bx) {
r = move(board, 0, rx, ry, 'R');
trX = tempx;
trY = tempy;
b = move(board, 0, bx, by, 'B');
tbX = tempx;
tbY = tempy;
}
else {
b = move(board, 0, bx, by, 'B');
tbX = tempx;
tbY = tempy;
r = move(board, 0, rx, ry, 'R');
trX = tempx;
trY = tempy;
}
if (b != true) {
if (r == true && result > time) {
result = time;
}
else
bfs(board, time + 1, trX, trY, tbX, tbY);
}
//print(board);
board = copy;
// to right
copy = board;
r = false;
b = false;
if (rx>bx) {
r = move(board, 1, rx, ry, 'R');
trX = tempx;
trY = tempy;
b = move(board, 1, bx, by, 'B');
tbX = tempx;
tbY = tempy;
}
else {
b = move(board, 1, bx, by, 'B');
tbX = tempx;
tbY = tempy;
r = move(board, 1, rx, ry, 'R');
trX = tempx;
trY = tempy;
}
if (b != true) {
if (r == true && result > time) {
result = time;
}
else
bfs(board, time + 1, trX, trY, tbX, tbY);
}
board = copy;
// to down
copy = board;
r = false;
b = false;
if (ry < by) {
r = move(board, 2, rx, ry, 'R');
trX = tempx;
trY = tempy;
b = move(board, 2, bx, by, 'B');
tbX = tempx;
tbY = tempy;
}
else {
b = move(board, 2, bx, by, 'B');
tbX = tempx;
tbY = tempy;
r = move(board, 2, rx, ry, 'R');
trX = tempx;
trY = tempy;
}
if (b != true) {
if (r == true && result > time) {
result = time;
}
else
bfs(board, time + 1, trX, trY, tbX, tbY);
}
board = copy;
// to up
copy = board;
r = false;
b = false;
if (ry > by) {
r = move(board, 3, rx, ry, 'R');
trX = tempx;
trY = tempy;
b = move(board, 3, bx, by, 'B');
tbX = tempx;
tbY = tempy;
}
else {
b = move(board, 3, bx, by, 'B');
tbX = tempx;
tbY = tempy;
r = move(board, 3, rx, ry, 'R');
trX = tempx;
trY = tempy;
}
if (b != true) {
if (r == true && result > time) {
result = time;
}
else
bfs(board, time + 1, trX, trY, tbX, tbY);
}
board = copy;
}
}
int main() {
cin >>y >> x;
int rx, ry, bx, by;
vector<vector<char>> board(y, vector<char>(x, 0));
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
cin >> board[i][j];
if (board[i][j] == 'R') {
rx = j;
ry = i;
}
if (board[i][j] == 'B') {
bx = j;
by = i;
}
}
}
bfs(board, 1, rx, ry, bx, by);
if (result <= 10)
cout << result;
else
cout << -1;
}
이번 문제는 뭔가 조잡하게 되어 버렸네요.;;
여기서 바로 전 방향으로 기울이는것을 스킵하면 시간 소비를 더 줄일 수 있습니다.
또한 길이적으로는 direction 을 for문으로 돌리면 길이를 좀 더 줄일 수 있습니다.