14442. 벽 부수고 이동하기 2

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

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

 

 

Solution

현재 상태에 대한 정보를 추가적으로 저장한다는 점에서 이전 포스팅에서 다룬 문제와 정확히 같은 유형의 문제입니다.

이전 포스팅과 매우 유사한 문제이기 때문에 소스코드를 짧게 설명하고 끝내도록 하겠습니다.

 

소스 코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
using namespace std;

vector<vector<char>> v(1001,vector<char>(1001));
bool check[1001][1001][11];
int n,m,k;
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

int bfs(int y,int x)
{
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push(make_pair(make_pair(y,x),make_pair(0,0)));
    check[y][x][0]=true;

    while(!q.empty())
    {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int cnt = q.front().second.first;
        int ans = q.front().second.second;

        if(y==n-1 && x==m-1)
        {
            return ans+1;
        }
        q.pop();

        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny>=0 && nx>=0 && ny<n && nx<m)
            {
                if(check[ny][nx][cnt+1]==false && v[ny][nx]=='1' &&cnt<k)
                {
                    q.push(make_pair(make_pair(ny,nx),make_pair(cnt+1,ans+1)));
                    check[ny][nx][cnt+1] = true;
                }
                else if(check[ny][nx][cnt]==false && v[ny][nx]=='0')
                {   
                    q.push(make_pair(make_pair(ny,nx),make_pair(cnt,ans+1)));
                    check[ny][nx][cnt]=true;
                
                }
            }
        }
    }


    return -1;
}
int main()
{
    FASTio;
    cin >> n >> m >> k;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin >> v[i][j];
        }
    }
    int ans = bfs(0,0);
    cout << ans;

    return 0;
}

마찬가지로 3차원 벡터 bool check를 만들어 주었습니다.

check[y][x][0] => 벽을 0번 부수고 (x,y) 좌표로 이동

check[y][x][1] => 벽을 1번 부수고 (x,y) 좌표로 이동

 

마찬가지로 queue에 현재 y좌표, x좌표, 벽 부순 횟수(다음좌표가 1인데 이동한 횟수), 총 이동 횟수를 저장하면서 BFS진행 

 

 

마찬가지로 현재 상태에 대한 정보를 추가적으로 저장한다는 아이디어만 있으면 쉽게 풀 수 있는 문제였습니다. 감사합니다.