[Algorithm] Baekjoon 5427번 : 불

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

5427번: 불

struct Node
{
    int y;
    int x;
};
 
char arr[1002][1002];
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] == '*') 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] == '@') continue;
            if (arr[nextY][nextX] == '*') continue;
 
            arr[nextY][nextX] = '@';
            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] == '*') continue;
 
            arr[nextY][nextX] = '*';
            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] != '*')
        {
            isEscaped = true;
            return;
        }
    }
 
    candidatePositions.clear();
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
 
    cin >> t;
 
    for (int k = 0; k < t; ++k)
    {
        humanPositions.clear();
        firePositions.clear();
        candidatePositions.clear();
        isEscaped = false;
        
        cin >> col >> row;
 
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                cin >> arr[i][j];
 
                if (arr[i][j] == '@')
                {
                    humanPositions.push_back({ i,j });
                }
                else if (arr[i][j] == '*')
                {
                    firePositions.push_back({ i,j });
                }
            }
        }
 
        if (checkEdge(humanPositions[0].y, humanPositions[0].x))
        {
            printf("1\n");
            continue;
        }
 
        bool isImpossible = false;
        int count = 0;
 
        while (1)
        {
            if (humanPositions.size() == 0)
            {
                isImpossible = true;
                break;
            }
 
            ++count;
 
            moveJ();
            spreadFire();
            checkCandidates();
 
            if (isEscaped) break;
        }
 
        if (isImpossible)
        {
            printf("IMPOSSIBLE\n");
        }
        else
        {
            printf("%d\n", count + 1);
        }
    }
}

바로 이전에 풀었던 불! 문제에서 테스트케이스 개수만 추가된거다.

그래서 굳이 글 안올리려했는데 실수했던게 있어서 안까먹으려고 올린다.

 

테스트케이스가 여러개 주어지는 문제에서는 main함수에서 return 사용하는것을 조심하자.

이전 문제에서 바로 탈출할 수 있으면 return 되게 해놨는데 이번 문제에서 안지워놔서 자꾸 12%에서 틀렸다고 뜨길래 조금 헤맸다..