※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
문제를 보면 상근이가 있는 칸에 불이 옮겨옴과 동시에 칸을 이동할 수 있다고 되어 있으므로, 빈 칸에 불과 상근이가 둘 다 올 수 있다면, 상근이는 그 칸에 갈 수 없음을 알아야 합니다.
따라서 상근이가 어느 입구를 최단 경로로 도착 하였을 때, 경로에 도착하는 데 사용된 가중치가 불이 도착하였을 때의 가중치보다 작아야만 탈출할 수 있게 됩니다.
그러므로 문제를 풀 때 각 출구에 대해 상근이와 불이 도착하는 데에 걸리는 최단 경로를 파악하여 한 번도 상근이가 먼저 도착한 적이 없다면 IMPOSSIBLE, 도착할 수 있다면 그 중 최솟값을 정답으로 출력하면 됩니다. 소스코드에서는 이것을 pair와 Node class의 재활용을 이용하여 다소 복잡하게 구현하였으나, visited 배열을 boolean 대신 int 형으로 하여 숫자를 카운트 해주는 방법도 있습니다.
참고로 이 문제에서 최단 경로를 찾을 때, 모든 경로간 이동 가중치가 1이므로 BFS 알고리즘에서 최초로 지점을 방문할 때의 가중치가 항상 최소가 됨을 알 수 있습니다. 그러므로 큐에 집어 넣기 전, 방문 여부를 체크해야 합니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<utility>
using namespace std;
bool visited[1001][1001];
class Node
{
public:
int x, y, cnt;
Node() { x = y = cnt = 2e9; }
Node(int x, int y, int cnt) : x(x), y(y), cnt(cnt) {}
};
queue<Node> q;
int w, h, pw, ph;
string s[1001];
map<pair<int, int>, Node> mp;
void run(char c)
{
for (int i = 0; i < w; i++)
for (int j = 0; j < h; j++)
if (s[i][j] == c)
{
pw = i, ph = j;
q.push({ i,j,1 });
visited[i][j] = true;
if(c=='@') break;
}
while (!q.empty())
{
auto here = q.front();
int x = here.x, y = here.y;
q.pop();
if (here.x == 0 || here.x == w - 1 || here.y == 0 || here.y == h - 1)
{
if (c == '@')
{
mp[{here.x, here.y}].x = here.cnt;
continue;
}
else if(here.cnt>1)
mp[{here.x, here.y}].y = here.cnt;
}
if (x > 0 && !visited[x - 1][y] && s[x - 1][y] == '.')
{
visited[x - 1][y] = true;
q.push({ x - 1,y,here.cnt + 1 });
}
if (x + 1 < w && !visited[x + 1][y] && s[x + 1][y] == '.')
{
visited[x + 1][y] = true;
q.push({ x + 1,y,here.cnt + 1 });
}
if (y > 0 && !visited[x][y - 1] && s[x][y - 1] == '.')
{
visited[x][y - 1] = true;
q.push({ x,y - 1,here.cnt + 1 });
}
if (y + 1 < h && !visited[x][y + 1] && s[x][y + 1] == '.')
{
visited[x][y + 1] = true;
q.push({ x,y + 1,here.cnt + 1 });
}
}
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> h >> w;
for (int i = 0; i < w; i++) cin >> s[i];
run('@');
memset(visited, 0, sizeof(visited));
s[pw][ph] = '.';
run('*');
memset(visited, 0, sizeof(visited));
bool chk = false;
int ans = 2e9;
for (auto it : mp)
{
if (it.second.x < it.second.y)
chk = true, ans = min(ans, it.second.x);
}
if (!chk) cout << "IMPOSSIBLE\n";
else cout << ans << "\n";
mp.clear();
}
}