문제
왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울여서 구슬을 꺼내는 게임
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있니?
생각
map이 주어지고, 최소 행동으로 탈출 문제니까 BFS
queue<pair<int, vector<pair<int, int>>>> q;
//count, ball info큐에 몇 번만에 만들었는지 count 저장,
처음에는 그때 그때 만들어진 map을 가지고 다닐까 생각했는데
장애물, 벽, 구멍 위치는 일정하니까
빨간, 파란 구슬의 위치만 pair<int, int> 벡터로 저장했다
구현하기 까다로웠던 점
'더 이상 구슬이 움직이지 않을 때 까지 기울인다는 것' 이 어려웠다
예를들어 오른쪽으로 기울이는 상황에
1. R.B. 는 ..RB 이 되게
2. RBO 는 두 개의 구슬이 다 구멍에 들어가서 실패 하게
구현하는 게 쉽지 않은거지
1-1.
처음에는 오른쪽으로 기울인다면 같은 높이에 있는지 확인하고,
같은 높이라면 오른쪽에 가까운 구슬을 먼저 이동시켜주었다
이렇게 구현을 하면 모든 경우를 나눠서 처리해줘야해서 너무 코드가 길어지고 더러워졌다
1-2.
그래서 더 생각해서 나온 아이디어가
먼저 구슬을 서로 신경쓰지 않고 각각 이동한 다음
두 구슬이 같은 위치에 있을 경우엔
변화량? 이동거리?가 큰 구슬이 멀리서 이동한 것이므로 한 칸 덜 오게했다
1-3.
친구는 두 구슬을 한 칸 한 칸씩 이동해줬다고 한다
깔끔하고 명확하고 좋은 것 같다
2.
빨간, 파란 구슬 통과 여부를 확인하는 변수 rflag, bflag를 사용해
구멍에 들어가면 true, 아직 안 들어갔으면 false로 표현
rflag가 true면 우리가 만들고 싶은 상태를 만든 것! 탐색 그만
bflag가 false면 이 상태를 q에 넣어주고, 가능한지 탐색을 계속한다
여기서 신경써줘야하는 건 두 개의 구슬이 다 구멍에 들어가는 상황
즉, rflag, bflag 둘 다 true인 경우인거지
나는 이때 rflag만 false로 만들어 주었다
그러면 rflag false : 아직 원하는 상태를 못 만들었으니 탐색을 하긴하는데
bflag ture : 이 상태는 더 탐색할 필요가 없음 인거지~~
또 신경써줘야할거는
rflag는 전역 변수로 처음만 false이고,
나중에 원하는 상태를 만들 수 있어서 true가 되면
BFS니까 바로 최단거리를 출력해주면되는데,
bflag는 기울일때마다 처음에 false로 초기화해주어야 한다
bflag가 true인 경우는 더 탐색할 필요가 없으므로
큐에 들어가있지도, 새로 넣어주지도 않을 것이니까
우리가 보는 모든 경우는 bflag가 false인 경우만임!!
//false로 제대로 안 바꿔줘서 rflag, bflag 둘 다 true로 인식해서 제대로 못 찾을 때 슬펐음
3. 그 외에도 방향 저장해서 다시 반대 방향으로 가는 걸 막음,
(위, 아래, 위, 아래 계속 반복되는 상황같은거)
만들었던 구슬 위치들 저장해놓고 만들었던 상태인지 확인,
기울였는데도 기존 상태와 차이가 없으면 탐색 그만,, 등등
반복되는 상태를 막는 걸 구현해준다
근데 이 문제는 10번 이상이면 신경 안 쓰는 거여서 대충해줘도 됐었다
이 설명 번호들 아래 코드에 주석으로 표현해놓겠음
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <utility>
using namespace std;
int n, m;
char orimap[15][15];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
queue<pair<int, vector<pair<int, int>>>> q;
//count, ball info
int rresult, bresult;
bool rflag;
void move(int count, vector<pair<int, int>> oriinfo) {
int rx = oriinfo[0].first;
int ry = oriinfo[0].second;
int bx = oriinfo[1].first;
int by = oriinfo[1].second;
for (int k = 0; k < 4; k++) {
vector<pair<int, int>> tempinfo = oriinfo;
bool bflag = false; //2
for (int i = 0; i < 2; i++) { //1
int nextx = tempinfo[i].first;
int nexty = tempinfo[i].second;
for (int j = 0; ; j++) {
nextx += dx[k];
nexty += dy[k];
if (orimap[nextx][nexty] == 'O') {
if (i) {
bflag = true;
bresult = count + 1;
}
else {
rflag = true;
rresult = count + 1;
}
break;
}
else if (orimap[nextx][nexty] != '.') {
tempinfo[i].first = nextx - dx[k];
tempinfo[i].second = nexty - dy[k];
break;
}
}
}
if (bflag && rflag) { //2
rflag = false;
}
if (rflag) {
break;
}
int nrx = tempinfo[0].first;
int nry = tempinfo[0].second;
int nbx = tempinfo[1].first;
int nby = tempinfo[1].second;
if (nrx == nbx && nry == nby) { //1
int diff0 = abs(rx - nrx + ry - nry);
int diff1 = abs(bx - nbx + by - nby);
if (diff0 > diff1) {
nrx -= dx[k];
nry -= dy[k];
tempinfo[0].first -= dx[k];
tempinfo[0].second -= dy[k];
}
else {
nbx -= dx[k];
nby -= dy[k];
tempinfo[1].first -= dx[k];
tempinfo[1].second -= dy[k];
}
}
if (!bflag) {
if (nrx != rx || nry != ry || nbx != bx || nby != by) { //3
q.push(make_pair(count + 1, tempinfo));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
pair<int, int> r, b, o;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> orimap[i][j];
if (orimap[i][j] == 'R') {
orimap[i][j] = '.';
r = make_pair(i, j);
}
else if (orimap[i][j] == 'B') {
orimap[i][j] = '.';
b = make_pair(i, j);
}
else if (orimap[i][j] == 'O') {
o = make_pair(i, j);
}
}
}
vector<pair<int, int>> startinfo;
startinfo.push_back(r);
startinfo.push_back(b);
q.push(make_pair(0, startinfo));
int result = -1;
while (!q.empty()) {
auto p = q.front();
q.pop();
int tempresult = p.first;
if (tempresult > 9) {
continue;
}
vector<pair<int, int>> tempinfo = p.second;
move(tempresult, tempinfo);
if (rflag) {
break;
}
}
if (rflag) {
cout << rresult;
}
else {
cout << -1;
}
return 0;
}