[Algorithm] Baekjoon 4179번 : 불!

https://www.acmicpc.net/problem/4179

4179번: 불!

 

struct Node
{
    int y;
    int x;
};
 
char arr[1001][1001];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int row, col;
bool isEscaped = false;
vector<Node> firePositions;
vector<Node> humanPositions;
vector<Node> candidatePositions;
 
bool checkEdge(int y, int x)
{
    if (y == 0 || y == row - 1)
    {
        return true;
    }
 
    if (x == 0 || x == col - 1)
    {
        return true;
    }
 
    return false;
}
 
void moveJ()
{
    vector<Node> temp;
 
    for (int i = 0; i < humanPositions.size(); ++i)
    {
        int curY = humanPositions[i].y;
        int curX = humanPositions[i].x;
 
        if (arr[curY][curX] == 'F') continue;
 
        for (int j = 0; j < 4; ++j)
        {
            int nextY = curY + dir[j][0];
            int nextX = curX + dir[j][1];
 
            if (nextY < 0 || nextY == row) continue;
            if (nextX < 0 || nextX == col) continue;
            if (arr[nextY][nextX] == '#') continue;
            if (arr[nextY][nextX] == 'J') continue;
            if (arr[nextY][nextX] == 'F') continue;
 
            arr[nextY][nextX] = 'J';
            temp.push_back({ nextY,nextX });
 
            if (checkEdge(nextY, nextX))
            {
                candidatePositions.push_back({ nextY,nextX });
            }
        }
    }
 
    humanPositions = temp;
}
 
void spreadFire()
{
    vector<Node> temp;
 
    for (int i = 0; i < firePositions.size(); ++i)
    {
        int curY = firePositions[i].y;
        int curX = firePositions[i].x;
 
        for (int j = 0; j < 4; ++j)
        {
            int nextY = curY + dir[j][0];
            int nextX = curX + dir[j][1];
 
            if (nextY < 0 || nextY == row) continue;
            if (nextX < 0 || nextX == col) continue;
            if (arr[nextY][nextX] == '#') continue;
            if (arr[nextY][nextX] == 'F') continue;
 
            arr[nextY][nextX] = 'F';
            temp.push_back({ nextY,nextX });
        }
    }
 
    firePositions = temp;
}
 
void checkCandidates()
{
    for (int i = 0; i < candidatePositions.size(); ++i)
    {
        int y = candidatePositions[i].y;
        int x = candidatePositions[i].x;
 
        if (arr[y][x] != 'F') 
        {
            isEscaped = true;
            return;
        }
    }
 
    candidatePositions.clear();
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> col;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 'J')
            {
                humanPositions.push_back({ i,j });
            }
            else if (arr[i][j] == 'F')
            {
                firePositions.push_back({ i,j });
            }
        }
    }
 
    if (checkEdge(humanPositions[0].y, humanPositions[0].x))
    {
        cout << 1;
        return 0;
    }
 
    bool isImpossible = false;
    int count = 0;
 
    while (1)
    {
        if (humanPositions.size() == 0)
        {
            isImpossible = true;
            break;
        }
        
        ++count;
 
        moveJ();
        spreadFire();
        checkCandidates();
 
        if (isEscaped) break;
    }
    
    if (isImpossible)
    {
        cout << "IMPOSSIBLE";
    }
    else
    {
        cout << count + 1;
    }
}

BFS문제인데 queue를 사용한게 아닌 그냥 vector로만 풀어봤다.

일단 순서는 지훈이를 먼저 이동시킨 후(노드를 퍼뜨린 후), 불을 확산시킨다(arr에 그대로 덮어씌워서 반영)

이 떄, 지훈이의 노드를 퍼뜨릴 때 퍼뜨릴 지점이 외각지점, 즉 탈출지점이면 일단 후보벡터에 넣어놓는다.

이렇게 하는 이유는 탈출 할 수 있는 지점이더라도 다음 불을 확산할 때 해당 지점이 확산되는 지점일 수 있기 때문이다.

 

그래서 바로 while문을 종료하는게  아니라 불을 확산시킨 후, 후보지점들이 불에의해 영향을 받은게 아니면 탈출할 수 있다고 판단한다.