작성일 : 2017-01-17 03:09:23
조회수 : 422



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


문제를 보면 상근이가 있는 칸에 불이 옮겨옴과 동시에 칸을 이동할 수 있다고 되어 있으므로, 빈 칸에 불과 상근이가 둘 다 올 수 있다면, 상근이는 그 칸에 갈 수 없음을 알아야 합니다.


따라서 상근이가 어느 입구를 최단 경로로 도착 하였을 때, 경로에 도착하는 데 사용된 가중치가 불이 도착하였을 때의 가중치보다 작아야만 탈출할 수 있게 됩니다.


그러므로 문제를 풀 때 각 출구에 대해 상근이와 불이 도착하는 데에 걸리는 최단 경로를 파악하여 한 번도 상근이가 먼저 도착한 적이 없다면 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();
    }
}

불 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글