[알고리즘] 벽 부수고 이동하기 2

구현 방식

• 이전에 풀었던 “벽 부수고 이동하기” 문제는 벽을 하나만 부술 수 있었지만,
• 이번에는 여러개의 벽을 부술 수 있다.
• 그래서 배열의 크기를 [N][M][K] 로 늘려주고, 벽을 부수는 부분을 for문으로 변경을 해주었다.
• 이전 코드에서는 벽을 하나만 부숴서 신경을 써주지 않았지만, 해당 위치에서 해당 개수만큼 벽을 부신 전적이 있다면 큐에 채워주면 안된다.

코드

• 최종 코드는 아래와 같다.

void solution(int N, int M,int K, vector<vector<int>>& graph);
void bfs(Status start, int N, int M, int K, vector<vector<int>>& graph);
bool canGo(int N, int M, Status s);
bool visited[1001][1001][11] = {};
vector<vector<vector<int>>> dist(1001,vector<vector<int>>(1001, vector<int>(11, INT_MAX)));

struct Status
{
	int y;
	int x;
	int crushWall;
};

void solution(int N, int M, int K, vector<vector<int>>& graph)
{
	Status start;
	start.y = 0;
	start.x = 0;
	start.crushWall = 0;
	bfs(start, N, M, K, graph);
	
	int result = INT_MAX;
	for (int k = 0; k <= K; k++)
	{
		result = min(result, dist[N - 1][M -1][k]);
	}

	if (result == INT_MAX)
		result = -1;
	cout << result;

	return;
}

void bfs(Status start,int N, int M, int K, vector<vector<int>>& graph)
{
	vector<pair<int,int>> Dirs = { {1, 0} , {0,1} , {-1,0} , {0,-1} };
	queue<Status> q;

	q.push(start);
	visited[start.y][start.x][start.crushWall] = true;
	dist[start.y][start.x][start.crushWall] = 1;
	while (!q.empty())
	{
		Status curr = q.front();
		q.pop();

		for (auto& dir : Dirs)
		{
			Status next = { curr.y + dir.first, curr.x + dir.second, curr.crushWall };
			if (canGo(N, M, next) && !visited[next.y][next.x][next.crushWall])
			{
				if (graph[next.y][next.x] == 0)
				{
					q.push(next);
					visited[next.y][next.x][next.crushWall] = true;
					dist[next.y][next.x][next.crushWall] = dist[curr.y][curr.x][curr.crushWall] + 1;
				}
				if (graph[next.y][next.x] == 1)
				{
					for (int i = next.crushWall + 1; i <= K; i++)
					{
						// 이전에 i 개수만큼 부셔서 해당 위치에 도착했던 적이 있다면 Skip!
						if (visited[next.y][next.x][i])
							continue;
						// 벽부수기!
						next.crushWall = i;
						q.push(next);
						visited[next.y][next.x][i] = true;
						dist[next.y][next.x][i] = dist[curr.y][curr.x][curr.crushWall] + 1;
					}
				}
			}
		}

	}
}

bool canGo(int N, int M, Status s)
{
	if (s.y < 0 || N <= s.y)
		return false;
	if (s.x < 0 || M <= s.x)
		return false;
	return true;
}