[Algorithm] Baekjoon 16933번 : 벽 부수고 이동하기3

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

16933번: 벽 부수고 이동하기 3

 

struct Node
{
    int y;
    int x;
    int breakCount;
    bool isNight;
};
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int row, col, breakCount;
int arr[1001][1001];
int visited[1001][1001][11][2];
 
int BFS()
{
    memset(visited, 0x3f, sizeof(visited));
    queue<Node> q;
    q.push({ 0,0,breakCount,false });
 
    for (int i = 0; i <= breakCount; ++i)
    {
        visited[0][0][i][0] = 1; // 낮
        visited[0][0][i][1] = 1; // 밤
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curBreakCount = q.front().breakCount;
        bool curIsNight = q.front().isNight;
        q.pop();
 
        if (curY == row - 1 && curX == col - 1)
        {
            int result = visited[curY][curX][curBreakCount][curIsNight];
            return result;
        }
 
        if (curIsNight) // 지금이 밤이라면, 제자리에 있을지 고려할만하다. 제자리에서 낮이됐을 때 이득볼 경우의 수가 존재하니까 (벽을 부술수있음)
        {
            if (visited[curY][curX][curBreakCount][1] + 1 < visited[curY][curX][curBreakCount][0]) // 낮이 됐을 때 더 적은횟수면.
            {
                visited[curY][curX][curBreakCount][0] = visited[curY][curX][curBreakCount][1] + 1;
                q.push({ curY,curX,curBreakCount,false });
            }
        }
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= row) continue;
            if (nextX < 0 || nextX >= col) continue;
 
            if (arr[nextY][nextX] == 0) // 다음이 빈공간이면 (낮이든 밤이든)
            {
                if (visited[nextY][nextX][curBreakCount][!curIsNight] > visited[curY][curX][curBreakCount][curIsNight] + 1) // 이전에 진입한놈은 더 많은 횟수로 진입했을 때,
                {
                    visited[nextY][nextX][curBreakCount][!curIsNight] = visited[curY][curX][curBreakCount][curIsNight] + 1;
                    q.push({ nextY,nextX,curBreakCount,!curIsNight });
                }
            }
            else // 다음이 벽이면
            {
                if (!curIsNight) // 그리고 낮이면 (낮에만 부술수있으니까)
                {
                    if (curBreakCount >= 1 && visited[nextY][nextX][curBreakCount - 1][!curIsNight] > visited[curY][curX][curBreakCount][curIsNight] + 1)
                    {
                        visited[nextY][nextX][curBreakCount - 1][!curIsNight] = visited[curY][curX][curBreakCount][curIsNight] + 1;
                        q.push({ nextY,nextX,curBreakCount - 1,!curIsNight });
                    }
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> col >> breakCount;
    string temp;
 
    for (int i = 0; i < row; ++i)
    {
        cin >> temp;
 
        for (int j = 0; j < col; ++j)
        {
            arr[i][j] = temp[j] - '0';
        }
    }
 
    int result = BFS();
 
    cout << result;
}
 

 

이전문제인 벽 부수고 이동하기2에서 '낮과 밤'이라는 조건이 추가된 문제이다.

일단 낮과 밤이라는 경우의수까지 고려하기 위해 visited를 [1001][1001][11][2]로 설정한다.

그리고 보면 이동하지 않고 제자리에서 시간을 보낼수도 있다고 한다.

즉, 낮일 때 제자리에 있으면 이동했을 때처럼 1을 카운팅하고 밤으로 바뀐다. 밤이면 낮으로 바뀐다.

 

그러면 제자리에 있을 때 이득인 경우에만 제자리에서 있기를 수행해야할 텐데, 문제에서의 조건을 보면 '낮일때만 벽을 부수기가 가능하다..'라는 조건이 있다.

만약 당장 벽을부수면 매우 빠르게 도착지점을 갈 수 있는데 밤이라서 못부순다고 생각해보자.

그러면 1을 카운팅하더라도 낮까지 기다리는게 이득이 있는 상황이 분명히 있다.

그렇기 때문에 현재 노드가 밤인 경우에만, 조건을 고려해서 낮까지 기다리는 노드를 큐에 넣는다 (무조건 넣는것은 아니다)

현재가 낮이라면 밤까지 기다려서 이득볼 수 있는 경우의수가 전혀 없으므로 무시한다.

나머지는 이전문제랑 동일하다.