[BAEKJOON] 11451. 팩맨
Posted on
문제 :
청호는 팩맨 게임을 하던 도중, 갑자기 팩맨이 분열하여 2마리가 되는 것을 보았다. 이 2마리의 팩맨은 서로 다른 위치에 있지만, 청호의 조이스틱 하나의 조작에 똑같이 반응하였다. 팩맨을 북쪽으로 가도록 조작하면 2마리의 팩맨이 모두 북쪽으로 이동하고, 동쪽으로 가도록 조작하면 역시 둘 다 동쪽으로 이동하였다. 그러나 팩맨은 자신의 앞에 벽이 있으면 이동하지 않는다.
팩맨이 두 마리이면 좋은 점이 있었다. 단 한 번의 움직임으로 2개의 점을 먹을 수 있는 것이다. 그러나, 청호는 두 마리를 동시 조작하려다 보니 머리가 아프기 시작했다. 또한 두 마리가 각각 유령에게 잡아먹히지 않게 하는 것도 만만치 않았다. 만약 팩맨이 유령과 마주치면 청호는 라이프를 하나 잃게 된다. 청호는 라이프가 5개뿐이고, 두 번째 팩맨은 죽으면 다시 되살아나지 못하기 때문에 두 팩맨을 최대한 빨리 한 장소로 합치기로 결심했다. 과연 이것이 가능할까?
입력 :
첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각각의 테스트 케이스에는
- 첫 번째 줄에 M, N (2 ≤ M, N ≤ 50)이 주어진다. M은 미로의 행 개수, N은 미로의 열 개수를 나타낸다.
-
다음 M개의 줄에 각각 N개의 문자로 미로가 주어진다. 문자는 {P, X, G, .} 중 하나이며 각각
- P는 팩맨을 의미한다.
- X는 벽을 의미한다.
- G는 유령을 의미한다.
- .은 빈칸을 의미한다.
각 미로에는 정확히 2마리의 팩맨이 존재한다.
출력 :
각 테스트 케이스에 대해서 정답을 한 줄에 출력한다. 만약 가능할 경우, 팩맨을 조작해야 하는 최소 횟수를 출력한 후, 그 다음에 조작해야 하는 방향을 순서대로 {N, E, S, W}를 사용하여 출력한다. 각각 북쪽, 동쪽, 남쪽, 서쪽을 의미한다. 정답이 여러 개일 경우 아무거나 출력한다. 만약 팩맨을 합치는 것이 불가능하다면 IMPOSSIBLE을 출력한다.
문제를 단순화하기 위해, 유령은 제자리에 가만히 있는다고 가정한다. 또한 팩맨이 화면 끝에서 밖으로 이동하면, 반대편에서 나타난다고 가정한다.
풀이 :
bfs를 활용해서 두 팩맨이 합쳐지는 경로를 탐색하는 문제인 듯 했다. 하지만 꽤나 애를 먹고 시간도 많이 소비했던 문제였다. 문제를 풀고나니 드는 생각은 우선 경로 탐색이라고 생각에 확신을 가지고 바로 코딩을 시작했기에 문제 요구사항을 제대로 파악하지 못했을 뿐더러 최단 경로에 해당하는 경로를 출력하는 부분에서도 상당히 애를 먹었다. 분명 더 깔끔하고 메모리 또한 덜 쓰는 방식이 존재할테니 시간이 지난 후 한번 더 풀어볼 생각이다. 우선 문제에서 실수하기 쉬운 짚고 넘어가야할 부분을 몇 개 캐치해 보았다.
- 지도(배열)의 상하좌우 끝에 도달하면 더이상 이동하지 못하는 것이 아니고 반대편 방향에서 나타난다. ⇒ 팩맨 게임을 떠올리면 쉬움.
- 두 개의 팩맨 중 하나가 벽면에 부딪쳐 이동하지 못하는 경우에는 나머지 하나의 팩맨은 이동시키고 하나는 멈춰 있도록 간주해야한다. ⇒ 물론 두개의 팩맨 모두가 벽면에 가로막히는 경우는 제자리에 있기 때문에 중복된 항목이 큐에 들어가지 않도록 예외처리 해줘야 함!
- 단순히 지나온 경로를 기록해두는 배열을 만들어서 저장하면 안된다. ⇒ 이 점에서 꽤나 많은 시간이 걸렸는데 팩맨이 두개인지라 두개가 서로 다른 위치인 경우에도 무수히 많이 존재하기 때문에 경로를 기록해둔다 한들 계속 덮어씌어져서 소용이 없어진다. 때문에 나는 그냥 큐에 저장할 때 경로도 함께 구조체에 넣어 저장했다. (경로가 길어져 메모리를 너무 잡아먹지 않을까 걱정했지만 생각외로 괜찮았음.)
이 외에는 bfs를 두 항목으로 탐색하는 것을 헷갈리지 않게 코딩한다면 나쁘지 않은 문제였다. 하지만 이번 기회로 한번 더 꼭 코딩을 할 때 어느 정도 설계를 해두고 짜야겠다라는 생각을 하게 되었다.
코드 :
코드 보기/접기
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <utility>
#include <string>
#define pii pair<int, int>
using namespace std;
struct qnode {
int x1;
int y1;
int x2;
int y2;
string route;
};
string rutans;
char map[50][50], dir[4] = { 'E', 'S', 'W', 'N' };
int di[4] = { 0, 1, 0, -1 }, dj[4] = { 1, 0, -1, 0 }, n, m;
bool visit[50][50][50][50];
int bfs(vector<pii> org) {
queue<qnode> q;
q.push(qnode{ org[0].first, org[0].second, org[1].first, org[1].second, "" });
visit[org[0].first][org[0].second][org[1].first][org[1].second] = true;
int size, count = 0, k, x1, y1, x2, y2, cmpx1, cmpy1, cmpx2, cmpy2;
string cur;
while (!q.empty()) {
count++;
size = q.size();
while (size--) {
x1 = q.front().x1; y1 = q.front().y1;
x2 = q.front().x2; y2 = q.front().y2;
cur = q.front().route;
q.pop();
for (k = 0; k < 4; k++) {
cmpx1 = (x1 + di[k] + n) % n; cmpy1 = (y1 + dj[k] + m) % m;
cmpx2 = (x2 + di[k] + n) % n; cmpy2 = (y2 + dj[k] + m) % m;
if (map[cmpx1][cmpy1] == 'X') { cmpx1 = x1; cmpy1 = y1; }
if (map[cmpx2][cmpy2] == 'X') { cmpx2 = x2; cmpy2 = y2; }
if (map[cmpx1][cmpy1] == '.' && map[cmpx2][cmpy2] == '.' && !visit[cmpx1][cmpy1][cmpx2][cmpy2]) {
visit[cmpx1][cmpy1][cmpx2][cmpy2] = true;
if (cmpx1 == cmpx2 && cmpy1 == cmpy2) {
rutans = cur + dir[k];
return count;
}
q.push(qnode{ cmpx1, cmpy1, cmpx2, cmpy2, cur + dir[k] });
}
}
}
}
return 0;
}
void testCase() {
vector<pii> pac;
int i, j, count;
cin >> n >> m;
memset(visit, false, sizeof(visit));
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 'P') {
map[i][j] = '.';
pac.push_back(pii(i, j));
}
}
count = bfs(pac);
if (count) {
cout << count << ' ' << rutans << '\n';
}
else cout << "IMPOSSIBLE" << '\n';
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int tc;
cin >> tc;
while (tc--)
testCase();
return 0;
}