https://www.acmicpc.net/problem/13460
문제
> 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다.
> 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
> 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다.
> 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다.
> 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다.
> 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다.
> 이때, 파란 구슬이 구멍에 들어가면 안 된다.
> 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다.
> 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
> 각각의 동작에서 공은 동시에 움직인다.
> 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.
> 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.
> 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
> 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.
> 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
> 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
접근
BFS를 사용해 구슬의 이동 경로를 탐색한다.
빨간구슬과 파란구슬의 이동을 함께 봐야하므로 큐에 빨간구슬의 r,c 파란구슬의 r,c와 판을 기울인 횟수까지 넣는다. 문제에 10번 이하라는 조건이 있기 때문이다.
사방탐색을 하는데 각 방향마다 while문으로 빨간구슬과 파란구슬의 좌표를 벽(#)이나 구멍(O)이 아닐 때까지 해당 방향으로 굴린다. 동시에 굴러간 거리를 각각 누적해둔다.
다 굴리고 멈췄으면 구슬들이 구멍에 들어갔는지 확인한다.
파란구슬이 구멍에 들어가면 무조건 실패이므로 이떄 continue해주고, 아니라면 빨간구슬이 구멍에 있는지 본다. 있다면 바로 성공이라 판을 기울인 횟수를 출력하고 끝낸다.
둘다 아니면 벽에 닿아 멈췄다는 뜻이므로 둘이 같은 위치에 겹쳐있나만 봐주면 된다. 이때 앞서 구한 굴러간 거리를 사용한다.
둘 중 더 긴거리가 더 멀리서 왔다는 뜻이므로 다른 구슬 보다 한칸 뒤에 있어야 한다. 이를 현 좌표에서 방향값을 하나 뺴주면 된다.
이 좌표를 기준으로 다시 탐색을 해야하므로 이 좌표를 큐에 넘기고 이어간다.
문제해결
> 판의 크기N과 M을 입력받고 board벡터를 선언해 판을 입력받는다.
> 방문처리를 위해 visited bool벡터를 선언하는데 4차원으로 빨간구슬의 r,c와 파란구슬의 r,c를 가진다.
> 입력을 받으며 빨간구슬, 파란구슬의 위치를 잡아두고 이를 시작점으로 BFS에 인자로 넘겨 시작한다.
> BFS 내부에서 사용하는 큐는 빨간구슬의 r,c와 파란구슬의 r,c 그리고 이동횟수 cnt 총 5가지의 상태를 가진다.
> 빨간구슬과 파란구슬의 시작위치를 가지고 시작하고 while문에서 이를 잡아 탐색한다.
> 문제 조건에 10번 이하로 끝내야하므로 fcnt가 10이상이면 continue로 탐색을 하지않는다.
> 사방탐색을 하는데 각 구슬이 겹쳤을 때를 위해 거리를 누적할 Rcnt,Bcnt변수를 선언한다.
> 구슬 각각 while문으로 해당 방향으로 벽이 아니며, 구멍이 아닐 때까지 굴러간다.
> 벽에 만났던, 구멍에 들어갔던 while문이 끝났으면 이를 확인한다.
> 파란구슬이 구멍에 있으면 무조건 실패이므로 continue해주고, 아니라면 빨간구슬이 구멍에 있다면 현재까지의 이동횟수 +1 해주고 끝낸다.
> 둘 다 아니면 벽에 닿아 멈췄으므로 두 구슬이 겹쳐있는지만 확인해주면 된다.
> 둘의 위치가 같으면 Rcnt와Bcnt를 비교해 더 큰 구슬을 한칸 뒤로 물러준다.
> 해당 처리가 끝난 뒤의 최종 위치를 큐에 넘겨 탐색을 이어간다.
> while문이 꺠지면 가능한 방법이 없다는 뜻이므로 -1을 출력한다.코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
pair<int, int> red, blue;
vector<vector<char>> board;
vector<vector<vector<vector<bool>>>> visited;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
struct state {
int Rr, Rc, Br, Bc, cnt;
};
void BFS(pair<int, int> R, pair<int, int> B) {
queue<state> q;
q.push({ R.first, R.second, B.first, B.second, 0 });
visited[R.first][R.second][B.first][B.second] = true;
while (!q.empty()) {
int fRr = q.front().Rr;
int fRc = q.front().Rc;
int fBr = q.front().Br;
int fBc = q.front().Bc;
int fcnt = q.front().cnt;
q.pop();
if (fcnt >= 10) continue;
for (int i = 0; i < 4; i++) {
int nRr = fRr;
int nRc = fRc;
int nBr = fBr;
int nBc = fBc;
int Rcnt = 0, Bcnt = 0; //빨구, 파구 이동거리
while (board[nRr + dir[i]][nRc + dic[i]] != '#' && board[nRr][nRc] != 'O') {
nRr += dir[i];
nRc += dic[i];
Rcnt++;
} //빨간구슬 이동
while (board[nBr + dir[i]][nBc + dic[i]] != '#' && board[nBr][nBc] != 'O') {
nBr += dir[i];
nBc += dic[i];
Bcnt++;
} //파란구슬 이동
if (board[nBr][nBc] == 'O') continue;
if (board[nRr][nRc] == 'O') {
cout << fcnt + 1 << '\n';
return;
}
if (nRr == nBr && nRc == nBc) {
if (Rcnt > Bcnt) {
nRr -= dir[i];
nRc -= dic[i];
}
else {
nBr -= dir[i];
nBc -= dic[i];
}
}
if (!visited[nRr][nRc][nBr][nBc]) {
q.push({ nRr, nRc, nBr, nBc, fcnt + 1 });
visited[nRr][nRc][nBr][nBc] = true;
}
}
}
cout << -1 << '\n';
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
board.resize(N, vector<char>(M));
visited.assign(N, vector<vector<vector<bool>>>(M, vector<vector<bool>>(N, vector<bool>(M, false))));
for (int i = 0; i < N; i++) {
string str;
cin >> str;
for (int j = 0; j < str.size(); j++) {
board[i][j] = str[j];
if (str[j] == 'R') red = { i,j };
if (str[j] == 'B') blue = { i,j };
}
}
BFS(red, blue);
}
후기
따져줄게 많아 복잡했고, 4차원을 처음써봐서 어지러웠지만 생각보다 어렵진않았다.
