[백준/BOJ] 백준 14442번 : 벽 부수고 이동하기 2

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

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

벽을 부술 수 있는 횟수가 남아 있을 때는 벽을 부수는 경우와 벽을 부수지 않는 경우 2가지를 고려하였고, 벽을 부술 수 있는 횟수가 남아 있지 않다면 벽을 부수지 않는 경우만 고려하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
using namespace std;

int n, m, k;
vector<string> board;
int discoverd[1000][1000][11];
int depth[1000][1000][11];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Pre()
{
	for (int i = 0; i < 1000; i++)
		for (int j = 0; j < 1000; j++)
			for (int k = 0; k < 11; k++)
				discoverd[i][j][k] = 0;
}

//start에서 dest로 가는 최단 거리를 구한다
int Solve(pair<pair<int, int>, int> start, pair<int, int> dest)
{
	discoverd[start.first.first][start.first.second][start.second] = 1;
	depth[start.first.first][start.first.second][start.second] = 0;

	queue<pair<pair<int, int>, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<pair<int, int>, int> here = q.front();
		q.pop();

		//목적지에 도착 했을때
		if (here.first.first == dest.first && here.first.second == dest.second)
			return depth[here.first.first][here.first.second][here.second] + 1;

		//벽을 부술 수 있는 횟수가 남아 있을때
		if (here.second > 0)
		{
			for (int i = 0; i < 4; i++)
			{
				pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dx_dy[i][0], here.first.second + dx_dy[i][1]), here.second - 1);

				if (there.first.first >= 0 && there.first.first < n && there.first.second >= 0 && there.first.second < m && discoverd[there.first.first][there.first.second][there.second] == 0)
				{
					discoverd[there.first.first][there.first.second][there.second] = 1;
					depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;

					q.push(there);
				}
			}
		}

		//벽을 부수지 않는 경우
		for (int i = 0; i < 4; i++)
		{
			pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dx_dy[i][0], here.first.second + dx_dy[i][1]), here.second);

			if (there.first.first >= 0 && there.first.first < n && there.first.second >= 0 && there.first.second < m && discoverd[there.first.first][there.first.second][there.second] == 0 && board[there.first.first][there.first.second] == '0')
			{
				discoverd[there.first.first][there.first.second][there.second] = 1;
				depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;

				q.push(there);
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;

	Pre();

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	//(0,0)에서 (n-1,m-1)로 가는 최단 거리를 구하는 문제로 풀었다
	//start에는 (0,0)의 위치뿐만 아니라 벽을 부술 수 있는 횟수도 저장했다
	pair<pair<int, int>, int> start = make_pair(make_pair(0, 0), k);
	pair<int, int> dest = make_pair(n - 1, m - 1);

	cout << Solve(start, dest);

	return 0;
}