[Algorithm] Baekjoon 14442번 : 벽 부수고 이동하기2

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

14442번: 벽 부수고 이동하기 2

struct Node
{
    int y;
    int x;
    int breakCount;
};
 
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];
 
int BFS()
{
    memset(visited, 0x3f, sizeof(visited));
    queue<Node> q;
    q.push({ 0,0,breakCount});
 
    for (int i = 0; i <= breakCount; ++i)
    {
        visited[0][0][i] = 1;
    }
    
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curBreakCount = q.front().breakCount;
        q.pop(); 
 
        if (curY == row - 1 && curX == col - 1)
        {
            int result = visited[curY][curX][curBreakCount];
            return result;
        }
 
        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] > visited[curY][curX][curBreakCount]+1) // 이전에 진입한놈은 더 많은 횟수로 진입했을 때
                {
                    visited[nextY][nextX][curBreakCount] = visited[curY][curX][curBreakCount] + 1;
                    q.push({ nextY,nextX,curBreakCount});
                }
            }
            else if (arr[nextY][nextX] == 1)// 벽이라면
            {
                if (curBreakCount >= 1 && visited[nextY][nextX][curBreakCount-1] > visited[curY][curX][curBreakCount]+1) 
                {    
                    visited[nextY][nextX][curBreakCount - 1] = visited[curY][curX][curBreakCount] + 1;
                    q.push({ nextY,nextX,curBreakCount - 1});
                }
            }
        }
    }
 
    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;
}

이전의 벽부수기문제에서 좀 더 응용단계의 문제이다.

이전 문제에서는 벽을 부수는 횟수가 한번밖에 안됐지만, 이번엔 k번의 횟수가 주어진다.

내가 작성한 코드의 노드는 y,x좌표와 '벽을 부술 수 있는 횟수'를 보유하고 있다.

 

접근하려는 공간이 빈공간이든 벽이든, 이전에 같은 조건의 노드가 접근했었는지 체크한다.

단순히 했다 안했다를 체크하는게 아니라, 현재 접근하려는 같은조건의 노드가 '이전의 같은 조건'의 노드보다 더 적은 횟수(거리)로 접근할 수 있는지를 체크하는 것이다. (정확히는 현재 노드의 카운트 +1을 기준으로 체크)

 

'이전에 같은조건의 노드가' 현재 접근하려는 노드의카운트+1보다 (접근할거면 +1할거니까)  작다면, 즉 이미 더 짧은횟수로 접근했었더라면 여기를 더이상 접근할 필요가 없기 때문이다. 

불필요한 노드를 큐에 넣어서 수행속도를 지연시키기 때문에 미리 방지하는 것이다.

 

접근하려는 칸이 벽일 때 if문에 visited[nextY][nextX][curBreakCount-1]로 되어있는 이유는, 만약 nextY nextX 좌표에 접근하게 된다면 벽을 부수고 접근하는 것이기 때문에 횟수를 한개 삭감시킨 좌표를 검사하는 것이다.