[BOJ] 13460 : 구슬 탈출 2
풀이
DFS, BFS
삼성 기출문제인 구슬 탈출 2를 DFS로 풀어보았다.
450라인이나 나왔다.(11805B 이다). 시간은 0ms이다.
하지만 BFS로 1/3코드로 푼것과 시간은 같다.
하하하하 나는 이제 시뮬레이션 문제가와도 비빌수가 있다.
아 백업할때 배열만 memcpy로 백업했어서 문제가 발생했었다.
백업할때 전역변수인 rx,ry,bx,by까지 갱신해주는것으로 해결했다.
항상 전역변수가 변할때는 주의를 기울여야겠다.
밑에는 BFS코드도 첨부한다. na982님 영상을 참고해서 풀었었다.
코드
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
char arr[10][10];
int ans = -1;
int rx,ry;
int bx,by;
int gx,gy;
int flag1;
int flag2;
//< ^ > v : 0 1 2 3
void move(int cmd) {
if (cmd == 0) {
//더왼쪽것부터 움직임
if (ry < by) {
while (1) {
int nx = rx;
int ny = ry - 1;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[rx][ry] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
while (1) {
int nx = bx;
int ny = by - 1;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
flag2 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
}
else {
while (1) {
int nx = bx;
int ny = by - 1;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
flag2 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
while (1) {
int nx = rx;
int ny = ry - 1;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[rx][ry] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
}
}
else if (cmd == 1) {
//더위쪽것부터 움직임
if (rx < bx) {
while (1) {
int nx = rx - 1;
int ny = ry;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[rx][ry] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
while (1) {
int nx = bx - 1;
int ny = by;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
flag2 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
}
else {
while (1) {
int nx = bx - 1;
int ny = by;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
flag2 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
while (1) {
int nx = rx - 1;
int ny = ry;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[rx][ry] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
}
}
else if (cmd == 2) {
//더오른쪽것부터 움직임
if (ry > by) {
while (1) {
int nx = rx;
int ny = ry + 1;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[rx][ry] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
while (1) {
int nx = bx;
int ny = by + 1;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
flag2 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
}
else {
while (1) {
int nx = bx;
int ny = by + 1;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
arr[rx][ry] = '.';
flag2 = 1;
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
while (1) {
int nx = rx;
int ny = ry + 1;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
}
}
else if (cmd == 3) {
//더아래쪽것부터 움직임
if (rx > bx) {
while (1) {
int nx = rx + 1;
int ny = ry;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
flag1 = 1;
arr[rx][ry] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
while (1) {
int nx = bx + 1;
int ny = by;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
flag2 = 1;
arr[bx][by] = '.';
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
}
else {
while (1) {
int nx = bx + 1;
int ny = by;
if (nx == gx && ny == gy) {
//B가 떨어지면 실패임
arr[bx][by] = '.';
flag2 = 1;
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'R') {
break;
}
arr[bx][by] = '.';
arr[nx][ny] = 'B';
bx = nx;
by = ny;
}
while (1) {
int nx = rx + 1;
int ny = ry;
if (nx == gx && ny == gy) {
//O면 blue도 같이 떨어지는지 체크해야함
arr[rx][ry] = '.';
flag1 = 1;
break;
}
else if (arr[nx][ny] == '#' || arr[nx][ny] == 'B') {
break;
}
arr[rx][ry] = '.';
arr[nx][ny] = 'R';
rx = nx;
ry = ny;
}
}
}
}
void go(int cnt, int cmd) {
if (cnt > 10 || (ans!=-1&&cnt>=ans)) {
return;
}
if(cmd!=-1)
move(cmd);
if (flag1 || flag2) {
if (!flag2) {
if (ans == -1 || ans > cnt) {
ans = cnt;
}
}
flag1 = 0;
flag2 = 0;
return;
}
/*
cout << cnt << ' ' << cmd <<' '<< ans<<'\n';
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << arr[i][j];
}
cout << '\n';
}
cout << '\n';
*/
char backup[10][10] = { 0 };
int nrx = rx, nry = ry, nbx = bx, nby = by;
memcpy(backup, arr, sizeof(arr));
for (int i = 0; i < 4; i++) {
if (i == 0 && i!=cmd && cmd!=2) {
go(cnt + 1, i);
}
else if (i == 1 && i != cmd && cmd != 3) {
go(cnt + 1, i);
}
else if (i == 2 && i != cmd && cmd != 0) {
go(cnt + 1, i);
}
else if (i == 3 && i != cmd && cmd != 1) {
go(cnt + 1, i);
}
memcpy(arr, backup, sizeof(arr));
rx = nrx;
ry = nry;
bx = nbx;
by = nby;
}
}
int main() {
cin >> n >> m;
char trash;
scanf("%c", &trash);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1c", &arr[i][j]);
if (arr[i][j] == 'R') {
rx = i;
ry = j;
}
if (arr[i][j] == 'B') {
bx = i;
by = j;
}
if (arr[i][j] == 'O') {
gx = i;
gy = j;
}
}
scanf("%c", &trash);
}
go(0,-1);
cout << ans;
return 0;
}
코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct Ball {
int rx, ry, bx, by, cnt;
};
Ball start;
char map[10][10];
//상, 하, 좌, 우
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
int bfs() {
int visited[10][10][10][10] = { 0 };
queue<Ball> q;
q.push(start);
visited[start.ry][start.rx][start.by][start.bx] = 1;
int ret = -1;
while (!q.empty()) {
Ball cur = q.front();
q.pop();
if (cur.cnt > 10)
break;
if (map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != 'O') {
ret = cur.cnt;
break;
}
for (int dir = 0; dir < 4; dir++) {
int next_ry = cur.ry;
int next_rx = cur.rx;
int next_by = cur.by;
int next_bx = cur.bx;
//빨간공
while (1) {
if (map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O') {
next_ry += dy[dir];
next_rx += dx[dir];
}
else {
if (map[next_ry][next_rx] == '#') {
next_ry -= dy[dir];
next_rx -= dx[dir];
}
break;
}
}
//파란공
while (1) {
if (map[next_by][next_bx] != '#' && map[next_by][next_bx] != 'O') {
next_by += dy[dir];
next_bx += dx[dir];
}
else {
if (map[next_by][next_bx] == '#') {
next_by -= dy[dir];
next_bx -= dx[dir];
}
break;
}
}
//같은위치에 겹친경우
if (next_rx == next_bx && next_ry == next_by) {
//O에 빠지는경우 제외(같이빠지면 -1)
if (map[next_ry][next_rx] != 'O') {
int r_distance = abs(next_ry - cur.ry) + abs(next_rx - cur.rx);
int b_distance = abs(next_by - cur.by) + abs(next_bx - cur.bx);
//빨간색이 더많이갔으면 뒤에따라가던친구니까 한칸뒤로
if (r_distance > b_distance) {
next_ry -= dy[dir];
next_rx -= dx[dir];
}
else {
next_by -= dy[dir];
next_bx -= dx[dir];
}
}
}
if (visited[next_ry][next_rx][next_by][next_bx] == 0) {
visited[next_ry][next_rx][next_by][next_bx] = 1;
Ball next;
next.ry = next_ry;
next.rx = next_rx;
next.by = next_by;
next.bx = next_bx;
next.cnt = cur.cnt + 1;
q.push(next);
}
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
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] == 'B') {
start.bx = j;
start.by = i;
}
else if (map[i][j] == 'R') {
start.rx = j;
start.ry = i;
}
}
}
start.cnt = 0;
int ret = bfs();
cout << ret;
return 0;
}
Written on April 9, 2019