불! 4179

문제

접근 방법

#	#	#	#
#	J	F	#
#	.	.	#
#	.	.	#

시작은 이럴 것이다.

#	#	#	#
#	1	F	#
#	2	3	#
#	3	4	#

J의 기준으로 갈 수 있는 곳은 이렇다.

#	#	#	#
#	2	1	#
#	3	2	#
#	4	3	#

F의 기준으론 이렇다. 불에 타는 곳은 F가 더 낮고 안전한 길은 J가 더 낮음을 확인할 수 있다.

#	#	#	#
#	J	.	#
#	.	F	#
#	.	.	#

이렇다면 어떨까?

#	#	#	#
#	1	2	#
#	2	F	#
#	3	4	#

J 기준

#	#	#	#
#	3	2	#
#	2	1	#
#	3	2	#

F 기준
J는 불에 타버릴 것이다. 같아도 안 된다는 것을 알게 됐다.

.	.	.	.	F
.	.	.	J	#
.	.	.	.	#
.	.	.	.	#
.	.	.	#	.

반례를 하나 가져왔다.

5	4	3	2	F
4	3	2	1	#
5	4	3	2	#
6	5	4	3	#
7	6	5	#	.

J 기준

5	4	3	2	1
6	5	4	3	#
7	6	5	4	#
8	7	6	5	#
9	8	7	#	.

F 기준
다른 경우를 확인해봐도 J 기준이 더 낮은 경우만 따지면 길이 보이는 것을 확인할 수 있다. 그렇다면 J는 목적지에 도달한 경우만 저장해두고 F는 목적지에 도달하면 값을 변형시켜 나중에 값을 확인할 때 표시해주면 되지 않을까 싶었다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int R, C, ret = 1001;
    cin >> R >> C;
    vector<vector<int>> map(R, vector<int>(C));
    queue<pair<int, int>> fBFS, jBFS, goal;

    for (int i = 0; i < R; ++i)
    {
        string col;
        cin >> col;
        for (int j = 0; j < C; ++j)
        {
            map[i][j] = col[j];
            switch (col[j])
            {
            case '.':
                map[i][j] = 0;
                break;
            case '#':
                map[i][j] = 1001;
                break;
            case 'F':
                map[i][j] = -1;
                fBFS.push({i, j});
                break;
            case 'J':
                if (i == R - 1 || j == C - 1 || i == 0 || j == 0)
                {
                    cout << 1;
                    exit(0);
                }
                map[i][j] = 1;
                jBFS.push({i, j});
                break;
            }
        }
    }
    while (!jBFS.empty())
    {
        auto jCur = jBFS.front();
        jBFS.pop();
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> jNext = {jCur.first + dy[i], jCur.second + dx[i]};
            if (jNext.first < 0 || jNext.second < 0 || jNext.first >= R || jNext.second >= C)
                continue;
            if (map[jNext.first][jNext.second] != 0)
                continue;
            if (jNext.first == R - 1 || jNext.second == C - 1 || jNext.first == 0 || jNext.second == 0)
            {
                goal.push(jNext);
            }
            map[jNext.first][jNext.second] = map[jCur.first][jCur.second] + 1;
            jBFS.push(jNext);
        }
    }
    while (!fBFS.empty())
    {
        auto fCur = fBFS.front();
        fBFS.pop();
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> fNext = {fCur.first + dy[i], fCur.second + dx[i]};
            if (fNext.first < 0 || fNext.second < 0 || fNext.first >= R || fNext.second >= C)
                continue;
            if (map[fNext.first][fNext.second] == 1001)
                continue;
            if (map[fNext.first][fNext.second] < abs(map[fCur.first][fCur.second] - 1))
                continue;
            map[fNext.first][fNext.second] = map[fCur.first][fCur.second] - 1;
            fBFS.push(fNext);
        }
    }
    while (!goal.empty())
    {
        auto cur = goal.front();
        goal.pop();
        if (map[cur.first][cur.second] > 0)
        {
            int number = map[cur.first][cur.second];
            if (ret > number)
                ret = number;
        }
    }
    if (ret == 1001)
        cout << "IMPOSSIBLE";
    else
        cout << ret;
    return 0;
}

풀이

이 문제에서 조심해야 할 건 2가지다.
불이 여러 개일 수 있다는 점.
시작부터 탈출지점일 수 있다는 점.
후자의 경우 예측은 했지만, 시작부터 탈출지점이면 0이 맞는지 1이 맞는지 모르겠고 혹시나 하는 마음에 안 작성했는데 덕분에 100퍼센트에서 틀리는 경우를 보게 해줬다.

사람의 경우 지나갈 수 있는 공간인 경우에만 탐색하게 하고
불의 경우 벽이 아니고 절댓값이 같거나 더 낮은 경우에만 탐색할 수 있게 해주면 된다. (불의 값<=사람의 값)