[13460] 구슬 탈출 2
풀이
최적화된 풀이인지는 모르겠지만 다음과 같은 알고리즘으로 풀면 정답을 받을 수 있습니다.
- R의 좌표를 rx, ry B의 좌표를 bx, by라고 할 때, queue<tuple<rx,ry,bx,by> > q;를 사용해서 BFS를 전개합니다. 이는 R와 B의 좌표를 동시에 다뤄야 함을 의미합니다. 2. 위에서 만든 Queue에는 R와 B의 시작 좌표 그리고 이 좌표에서부터 특정 방향으로 기울였을 때 R와 B가 멈추는 위치가 다시 Push됩니다. 3. 최단 경로를 찾아야 하므로 while(!q.empty()) -> int qs = q.size() -> qs번 for문 실행 -> 그 안에서 dx dy 4 방향으로 점검을 해야합니다.( 이 부분이 무슨 말인지 모르겠으면 아래 코드를 보면 됩니다.)
- 2번에서 Push를 현재의 위치에서 특정 방향으로 움직이는 것은 더이상 움직이지 못하는 경우가 될 때까지 계속 움직입니다. 더이상 움직이지 못하는 경우는 두 가지 입니다. 벽을 만나거나 구멍에 빠졌을 때 입니다.
- R와 B를 움직일 때는 R와 B를 겹치는 것은 나중에 판단하고 R와 B를 각각 벽을 만나지도 않고, 구멍에 빠지지도 않는 경우인지 판단하고 멈출 때까지 이동시킵니다.
- 만약 R와 B가 멈춘 위치가 같다면 R와 B중 욺직인 거리가 더 큰 것을 뒤로 한 칸 뺴서 겹치지 않도록 해줍니다. #00R00B00# -(오른쪽으로 기울이기)-> #000000RB#
- 이렇게 최종적으로 R과 B가 멈춘 위치를 방문했다고 표시합니다.
- R만 O에 도착했고, B는 아니라면 정답, 둘 다 O에 도착했다면 종료. 둘 다 O가 아니라면 q에 push합니다.
- 3번을 진행하다가 10번째까지 움직인 경우 프로그램을 종료합니다.
특징
- map이 2차원일 때 check 배열을 2차원 이상으로 구성해서 풀 수도 있다.
- na,nb,nc,nd를 생성할 때 어차피 #를 만나면 멈출 것이므로, 맵의 가장자리가 모두 #로 주어질 때는 인덱스 초과 구문을 짜지 않아도 된다.
- 입력값이 주어지는 모습을 보고 R,B,O가 각각 주어져야하므로 주어지는 값부터 R,B,O가 겹치는 경우는 고려하지 않아도 된다.
- 풀이를 보고 이해 다 하고, 그대로 짜는 것만 1시간이 걸렸고 3번의 실패를 틀렸습니다. 를 받았다.
코드
#include <cstdio>
#include <queue>
#include <tuple>
#include <algorithm>
#define MAX 10
using namespace std;
char map[MAX + 1][MAX + 1];
int n = 0, m = 0;
queue<tuple<int, int, int, int> > q;
//우, 좌, 하, 상
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool check[MAX + 1][MAX + 1][MAX + 1][MAX + 1];
int bfs(int a, int b, int c, int d) {
int ca = 0, cb = 0, cc = 0, cd = 0; //curr
int na = 0, nb = 0, nc = 0, nd = 0; //next
int ans = 1;
q.push(make_tuple(a, b, c, d));
check[a][b][c][d] = true;
while (!q.empty()) {
int qs = q.size();
for (int s = 0; s < qs; s++) {
tie(ca, cb, cc, cd) = q.front(); q.pop();
for (int k = 0; k < 4; k++) {
tie(na, nb, nc, nd) = tie(ca, cb, cc, cd);
//벽을 만나거나 구멍에 빠지지 않는다면 k방향으로 끝까지 움직이기
while (map[na + dx[k]][nb + dy[k]] != '#' && map[na][nb] != 'O') {
na += dx[k]; nb += dy[k];
}
while (map[nc+dx[k]][nd+dy[k]] != '#' && map[nc][nd] != 'O') {
nc += dx[k]; nd += dy[k];
}
//printf("NEXT %d, %d, %d, %d\n", na, nb, nc, nd);
if (na == nc && nb == nd) {
//둘 다 구멍에 빠진 경우
if (map[na][nb] == 'O') continue;
//겹치면 더 많이 움직인 것을 뒤로 한 칸 빼주기
if (abs(na - ca) + abs(nb - cb) > abs(nc - cc) + abs(nd - cd)) {
na -= dx[k]; nb -= dy[k];
}
else {
nc -= dx[k]; nd -= dy[k];
}
}
//B가 구멍에 빠진 경우는 제외
if (map[nc][nd] == 'O') continue;
//R만 구멍에 빠진 경우는 정답
if (map[na][nb] == 'O') return ans;
//둘 다 구멍에 빠지지 않았으면
if (check[na][nb][nc][nd] == false) {
check[na][nb][nc][nd] = true;
q.push(make_tuple(na, nb, nc, nd));
}
}
}
if (ans == 10) {
return -1;
}
ans += 1;
}
return -1;
}
int main(void) {
int a = 0, b = 0, c = 0, d = 0; //a,b = R, c,d = B
scanf("%d%d", &n, &m); getchar();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%c", &map[i][j]);
if (map[i][j] == 'R') {
a = i; b = j;
}
else if (map[i][j] == 'B') {
c = i; d = j;
}
}
getchar();
}
printf("%d\n", bfs(a,b,c,d));
return 0;
}