[백준] 13460 구슬 탈출 2
[문제이해]
1. 맵에는 벽(#), 빨간구슬(R), 파란구슬(B), 구멍(O)이 각각 1개씩 존재한다.
2. 4가지 기울이기(왼쪽, 오른쪽, 위쪽, 아래쪽)를 통해 구슬을 굴릴 수 있다.
- 빨간구슬이 구멍에 빠지면 성공
- 파란구슬이 구멍에 빠지면 실패
- 빨간구슬과 파란구슬 모두 구멍에 빠져도 실패
- 기울이기를 10번 초과하면 실패
3. 보드의 상태가 주어졌을 때 최소 몇 번만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지를 계산해야한다.
[설계]
1. 빨간구슬과 파란구슬에 대해 상,하,좌,우 4방향 BFS를 적용한다.
2. 예를들어 맵을 오른쪽으로 기울였으면, 빨간구슬과 파란구슬 둘 다 오른쪽 방향 BFS를 적용한다.
3. 큐에다가 빨간구슬 x, y 좌표와 파란구슬 x, y 좌표 그리고 기울인 횟수 d를 넣어준다.
3. 기울이고 나서 구슬의 위치는 4차원 배열로 방문처리해둔다. bool visited[rx][ry][bx][by];
4. 구슬은 벽(#)을 만날때까지 굴러가야한다. 구슬에 대해 BFS를 적용할 때 이 부분을 처리해야한다.
5. 구슬이 서로 붙어 있는 경우를 고려해야한다. 더 멀리 이동한 구슬을 움직인 방향을 기준으로 한 칸 뒤로 배치시킨다.
6. 실패하면, -1을 출력 해야한다.
[회고]
1. BFS를 사용하는 이유?
-> 최소한의 기울임으로 빨간 구슬을 구멍에 빠뜨려야한다.
-> BFS는 가중치가 없는 그래프에서 최단경로를 찾을 때 사용되므로 위 문제에 적용될 수 있다.
2. 빨간 구슬과 파란구슬이 붙어있는 경우를 고려해야함
-> 처음에 생각지 못해서 어려웠다.
3. 4차원 배열을 통해 방문 처리
-> 처음에 빨간구슬 2차원 방문 배열, 파란구슬 2차원 방문 배열 이렇게 나눠서함
-> 빨간 구슬과 파란 구슬이 동시에 움직이기 때문에 4차원 배열을 사용해서 한 번에 방문 처리해야함.
[코드]
#include<iostream>
#include<queue>
using namespace std;
typedef struct {
int rx, ry, bx, by, d;
}pos;
char map[10][10];
int n, m;
int res = 11;
bool visited[10][10][10][10];
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
queue<pos> q;
void move(int &x, int &y, int &Cnt, int dx, int dy) {
while (map[x+dx][y+dy] != '#' && map[x][y] != 'O'){
x += dx;
y += dy;
Cnt++;
}
}
void bfs() {
while (!q.empty()) {
int rx = q.front().rx, ry = q.front().ry;
int bx = q.front().bx, by = q.front().by;
int d = q.front().d;
q.pop();
if (d >= 10) continue;//기울인 횟수가 10이상이라면, 스킵한다.
for (int i = 0; i < 4; i++) {
int nrx = rx, nry = ry; //빨강 구슬의 새로운 좌표
int nbx = bx, nby = by; //파란 구슬의 새로운 좌표
int rCnt = 0, bCnt = 0; //빨강, 파랑 구슬이 굴러간 횟수를 카운트 하는 변수
move(nrx, nry, rCnt, dx[i], dy[i]); //빨간구슬 이동
move(nbx, nby, bCnt, dx[i], dy[i]); //파란구슬 이동
if (map[nbx][nby] == 'O') //파란 구슬이 구멍에 빠지면, 실패
continue;
if (map[nrx][nry] == 'O') {//빨간 구슬만 구멍에 빠진 경우라면, 성공
res = min(res, d+1);//성공 했을 때, 최솟값 기록
continue;
}
if (nrx == nbx && nry==nby) {//구슬이 겹치는 경우 = 구슬이 붙어있는 경우
if (bCnt > rCnt) { //파란구슬이 더 멀리 갔다면, 한 칸 뒤로
nbx -= dx[i];
nby -= dy[i];
}
else { //빨간구슬이 더 멀리 갔다면, 한 칸 뒤로
nrx -= dx[i];
nry -= dy[i];
}
}
if (visited[nrx][nry][nbx][nby]) continue; //이미 방문했다면(이미 알아본 경우의 수라면), 스킵
visited[nrx][nry][nbx][nby] = true; //방문처리
q.push({ nrx,nry,nbx,nby,d+1}); //다시 큐에 넣는다.
}
}
}
int main() {
cin >> n >> m;
int rx, ry, bx, by; //빨간구슬과 파란구슬의 초기위치 값을 저장하는 변수
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 'R') {
rx = i, ry = j;
}
else if (map[i][j] == 'B') {
bx = i, by = j;
}
}
}
visited[rx][ry][bx][by]=true;
q.push({ rx,ry,bx,by,0 }); //두 구슬의 초기위치, 기울인횟수(0)을 큐에 넣어준다.
bfs();
if(res == 11)
printf("-1");
else
printf("%d", res);
return 0;
}
[출처]