문제 설명
bfs 최단거리 문제이면서, 공이 두개라서 구현이 까다롭다.
이동 함수
4 방향으로 이동했을때,
빨간공과 파란 공의 위치를 return해주는 함수를 만들었다.
항상 바깥쪽에는 벽이 있기 때문에 밖으로 떨어질 일은 없으니 벽과 만날때까지 이동시켜준다.
- 중간에 공이 구멍으로 들어가면 특별하게 처리해주기 위해서, 좌표를 음수로 표기해준다.
만약 파란 공과 빨간 공의 위치까지 생각해서 구현하려면 아주 복잡하고 길어지는데,
그렇게 하지 말고 무시하고 이동 한 후, 두 공의 좌표가 같다면 처리를 해주면 된다.
- 처리 방법
- 아래 상태에서 오른쪽으로 간다고 해보자.
- R . . . B . . #
- 그냥 이동을 하면 R과 B가 같은 위치에 찍힐 것이다.
- . . . . . . (RB) #
- 같은 위치라면, 방향에 따라서 뒤따라오던 애를 한칸 전으로 돌리면 된다.
- . . . . . R B #
cpp
// 아래, 위, 오른, 왼
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
tuple<int,int,int,int> go(int dir, int rx, int ry, int bx, int by){
int nrx=rx, nry=ry, nbx=bx, nby=by;
// Red
while(true){
nrx+=dx[dir]; nry+=dy[dir];
if (board[nrx][nry]=='#') {
nrx-=dx[dir]; nry-=dy[dir];
break;
}
// 구멍으로 빠짐 : -1로 표시
if (board[nrx][nry]=='O'){
nrx = -1; nry = -1;
break;
}
}
// Blue
while(true){
nbx+=dx[dir]; nby+=dy[dir];
if (board[nbx][nby]=='#') {
nbx-=dx[dir]; nby-=dy[dir];
break;
}
// 구멍으로 빠짐 : -2로 표시
if (board[nbx][nby]=='O'){
nbx = -2; nby = -2;
break;
}
}
// 두 좌표가 같다면 겹칠 수 없으므로 처리
if(nrx==nbx && nry==nby){
// 아래로 내려간거라면 위에있던걸 한단계 전으로
if (dir==0){
if (bx<rx) nbx -= dx[dir];
else nrx -= dx[dir];
}
// 위로 올라간거라면 아래있던걸 한단계 전으로
else if (dir==1){
if (bx>rx) nbx -= dx[dir];
else nrx -= dx[dir];
}
// 오른쪽으로 간거라면 왼쪽에 있던걸 한단계 전으로
else if (dir==2){
if (by<ry) nby -= dy[dir];
else nry -= dy[dir];
}
// 왼쪽으로 간거라면 오른쪽에 있던걸 한단계 전으로
else if (dir==3){
if (by>ry) nby -= dy[dir];
else nry -= dy[dir];
}
}
return {nrx, nry, nbx, nby};
}BFS 최단거리
BFS 이기 때문에 dist가 낮은 것부터 처리된다.
10번 안에 도착하지 못하는 경우 바로 종료시켜주면 된다.
위 go 함수를 통해 B의 x좌표가 -2가 되었다면 빠진 것이므로, 더이상 진행하지 않고 다음 큐로 이동한다.
B는 안빠지면서 R의 x좌표가 -1이면 성공한것이므로 dist+1 을 리턴한다.
cpp
int bfs(int start_rx, int start_ry, int start_bx, int start_by){
// Red 좌표, Blue좌표, 거리
queue<tuple<int,int,int,int,int>> q;
q.push({start_rx, start_ry, start_bx, start_by, 0});
visited[start_rx][start_ry][start_bx][start_by]=true;
while (!q.empty()){
auto [rx, ry, bx, by, now_dist] = q.front();
// 10번 안에 도착 못했을 경우
// 10도 포함해야하는 이유 : 지금까지 온게 10이면,
// 다음단계에 도달해도 return은 11이 되기 때문에
if (now_dist>=10) {
return -1;
}
q.pop();
for (int i=0; i<4; i++){
// 이동
auto [nrx, nry, nbx, nby] = go(i, rx, ry, bx, by);
// 파란색이 구멍에 빠짐
if (nbx==-2) continue;
// 파란색은 안빠지고 빨간색이 구멍에 빠지면 종료
if (nrx==-1) return now_dist+1;
if (visited[nrx][nry][nbx][nby]) continue;
visited[nrx][nry][nbx][nby] = true;
q.push({nrx, nry, nbx, nby, now_dist + 1});
}
}
return -1; // 도달 못했을 경우
}내 풀이
cpp
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const int INF = 0x7f7f7f7f;
/*--
<https://www.acmicpc.net/problem/13460>
상하좌우로 기울여서
R이 O로 들어가야함.
동시에 R, B 가 들어가면 안됨
#은 장애물, .은 빈공간
*/
#define MAX 10
int N, M;
char board[MAX][MAX];
bool visited[MAX][MAX][MAX][MAX]; // 빨간 구슬, 파란구슬
// 아래, 위, 오른, 왼
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
tuple<int,int,int,int> go(int dir, int rx, int ry, int bx, int by){
int nrx=rx, nry=ry, nbx=bx, nby=by;
// Red
while(true){
nrx+=dx[dir]; nry+=dy[dir];
if (board[nrx][nry]=='#') {
nrx-=dx[dir]; nry-=dy[dir];
break;
}
// 구멍으로 빠짐 : -1로 표시
if (board[nrx][nry]=='O'){
nrx = -1; nry = -1;
break;
}
}
// Blue
while(true){
nbx+=dx[dir]; nby+=dy[dir];
if (board[nbx][nby]=='#') {
nbx-=dx[dir]; nby-=dy[dir];
break;
}
// 구멍으로 빠짐 : -2로 표시
if (board[nbx][nby]=='O'){
nbx = -2; nby = -2;
break;
}
}
// 두 좌표가 같다면 겹칠 수 없으므로 처리
if(nrx==nbx && nry==nby){
// 아래로 내려간거라면 위에있던걸 한단계 전으로
if (dir==0){
if (bx<rx) nbx -= dx[dir];
else nrx -= dx[dir];
}
// 위로 올라간거라면 아래있던걸 한단계 전으로
else if (dir==1){
if (bx>rx) nbx -= dx[dir];
else nrx -= dx[dir];
}
// 오른쪽으로 간거라면 왼쪽에 있던걸 한단계 전으로
else if (dir==2){
if (by<ry) nby -= dy[dir];
else nry -= dy[dir];
}
// 왼쪽으로 간거라면 오른쪽에 있던걸 한단계 전으로
else if (dir==3){
if (by>ry) nby -= dy[dir];
else nry -= dy[dir];
}
}
return {nrx, nry, nbx, nby};
}
int bfs(int start_rx, int start_ry, int start_bx, int start_by){
// Red 좌표, Blue좌표, 거리
queue<tuple<int,int,int,int,int>> q;
q.push({start_rx, start_ry, start_bx, start_by, 0});
visited[start_rx][start_ry][start_bx][start_by]=true;
while (!q.empty()){
auto [rx, ry, bx, by, now_dist] = q.front();
// 10번 안에 도착 못했을 경우
// 10도 포함해야하는 이유 : 지금까지 온게 10이면,
// 다음단계에 도달해도 return은 11이 되기 때문에
if (now_dist>=10) {
return -1;
}
q.pop();
for (int i=0; i<4; i++){
// 이동
auto [nrx, nry, nbx, nby] = go(i, rx, ry, bx, by);
// 파란색이 구멍에 빠짐
if (nbx==-2) continue;
// 파란색은 안빠지고 빨간색이 구멍에 빠지면 종료
if (nrx==-1) return now_dist+1;
if (visited[nrx][nry][nbx][nby]) continue;
visited[nrx][nry][nbx][nby] = true;
q.push({nrx, nry, nbx, nby, now_dist + 1});
}
}
return -1; // 도달 못했을 경우
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
cin >> board[i][j];
}
}
// 시작 지점 찾기
int rx, ry, bx, by;
for (int i=0; i<N; i++)
for (int j=0; j<M; j++)
if (board[i][j]=='R'){
rx = i; ry = j; break;
}
for (int i=0; i<N; i++)
for (int j=0; j<M; j++)
if (board[i][j]=='B'){
bx = i; by = j; break;
}
cout << bfs(rx, ry, bx, by);
return 0;
}마무리
내가 풀고도 빨간 공과 파란 공이 만날때 처리를 잘 해준 것 같아서 만족했다.