[Algorithm/C++17] 백준 14442 벽 부수고 이동하기 2

문제

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

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

풀이 방법

2206번 벽 부수고 이동하기와 비슷한 문제다. 이 문제에서는 벽을 K개만큼 부술 수 있는게 차이점이다. 비슷하게 풀되 벽을 1개까지 부쉈던 부분을 K개까지 부술 수 있게 처리하면 된다. 

코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vector<vector<int>> v(N+1, vector<int>(M+1, 0));
    int visited[1001][1001][11] = { 0 };
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            int t;
            scanf("%1d", &t);
            v[i][j] = t;
        }
    }
    bool success = false;
    queue<tuple<int, int, int>> q;
    q.push({1, 1, 0});
    for(int i=0; i<=K; i++)
        visited[1][1][i] = 1;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int y = get<0>(t);
        int x = get<1>(t);
        int crash = get<2>(t);
        if(y==N && x==M)
        {
            success = true;
            printf("%d", visited[y][x][crash]);
            break;
        }
        if(success) break;
        for(int i=0; i<4; i++)
        {
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(1<=ny && ny<=N && 1<=nx && nx<=M)
            {
            	if(v[ny][nx] == 0 && visited[ny][nx][crash] == 0)
            	{
            		visited[ny][nx][crash] = visited[y][x][crash]+1;
            		q.push({ny,nx,crash});
            	}
            	else if(v[ny][nx] == 1 && visited[ny][nx][crash+1] == 0 && crash < K)
            	{
            		visited[ny][nx][crash+1] = visited[y][x][crash]+1;
            		q.push({ny,nx,crash+1});
            	}
            }
        }
    }
    if(!success)
        printf("-1");
    return 0;
}

고찰

기존 2206번 풀이 코드에서 출력과 새로운 노드 탐색 시 방문 여부 조건문을 바꿨다. 

 

출력은 while문 안에서 목적지까지 도달했을 때 바로 출력한다. 이렇게 하지 않으면 while 문 밖에서 for문을 돌면서 visited배열에서 방문한 값들 중 최소값을 찾아야 한다. 

 

방문 여부 조건문은 원래 다음과 같이 작성했다.

if(1<=ny && ny<=N && 1<=nx && nx<=M)
{
    if(visited[ny][nx][crash] !=0) continue;
    if(v[ny][nx] == 0)
    {
        visited[ny][nx][crash] = visited[y][x][crash]+1;
        q.push({ny,nx,crash});
    }
    else if(v[ny][nx] == 1 && crash < K)
    {
        visited[ny][nx][crash+1] = visited[y][x][crash]+1;
        q.push({ny,nx,crash+1});
    }
}

이렇게 하면 벽을 탐색할 때 이미 부순곳도 또 부수고 탐색하려하기 때문에 시간 초과가 발생한다. 따라서 벽인 경우의 방문체크와 벽이 아닌 경우의 방문 체크를 다음과 같이 따로 해주었다.

if(1<=ny && ny<=N && 1<=nx && nx<=M)
{
    if(v[ny][nx] == 0 && visited[ny][nx][crash] == 0)
    {
        visited[ny][nx][crash] = visited[y][x][crash]+1;
        q.push({ny,nx,crash});
    }
    else if(v[ny][nx] == 1 && visited[ny][nx][crash+1] == 0 && crash < K)
    {
        visited[ny][nx][crash+1] = visited[y][x][crash]+1;
        q.push({ny,nx,crash+1});
    }
}