BOJ 14442 벽 부수고 이동하기 2

 

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

#문제접근

2차원 배열의 변수명 stepandblock[y][x] 는 y와 x 에 도달하기 까지 최단 거리와 부순 벽의 갯수를 저장합니다. 그래서 stepandblock에 저장된 거리와 벽의 갯수와 비교를 해가며 적어도 하나의 변화점이 생길경우 예를 들어 저장된 최단거리보다 더 짧은 거리일 경우 혹은 부순 벽의 갯수가 훨씬 적은 경우 bfs에 push를 해주고 새로 갱신해줍니다. 그렇게 구현한 뒤 bfs를 구현하게 되면 stepandblock[y][x]는 {y,x} 좌표에 도달할때 최단거리 그리고 벽의 갯수가 저장되게 되는데 bfs가 완료하게 되면 y x에는 부순 벽의 갯수가 아닌 최단 거리를 기준으로 데이터가 갱신이 완료됩니다.

그 후 while문 밖에서 기존의 초기화에서 INT_MAX값일 경우 -1을 출력하게 되고 INT_MAX값이 아니라면 저장된 최단거리를 출력했습니다.

 

#정답코드

 

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <climits>
#include <algorithm>
using namespace std;

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

struct info {
	std::pair<int, int> pos;
	int step;
	int block_cnt;
	info(const std::pair<int, int> pos, int step, int block_cnt) :pos(pos), step(step), block_cnt(block_cnt)
	{}
};



int main() {

	int N, M, K;
	cin >> N >> M >> K;
	std::vector<std::string> arr(N);
	for (auto& ele : arr)
		cin >> ele;

	std::deque<info> bfs;
	bfs.push_back(info({ 0,0 }, 0, 0));
	std::vector<std::vector<std::pair<int, int> > > stepandblock(N, std::vector<std::pair<int, int> >(M, { INT_MAX,INT_MAX }));//first는 step , second는 block갯수로 하자


	stepandblock[0][0].first = 0;
	stepandblock[0][0].second = 0;

	while (!bfs.empty()) {
		auto p = bfs.front();
		bfs.pop_front();

		//최단경로이니까 우선 최단거리일때 같은 경우에는 더 부술수 있는 것이 좋겠지

		for (int i = 0; i < 4; i++) {
			int py = p.pos.first + dy[i];
			int px = p.pos.second + dx[i];
			int pstep = p.step + 1;
			if (0 <= py && py < N && 0 <= px && px < M) {//범위 안에 있을 경우
				int pblock = p.block_cnt + arr[py][px] - '0';

				if (pblock <= K && ((pblock < stepandblock[py][px].second) + (stepandblock[py][px].first > pstep))>=1 ) {
					bfs.push_back(info({ py,px }, pstep, pblock));
					stepandblock[py][px].first = min(stepandblock[py][px].first,pstep);
					stepandblock[py][px].second = min(stepandblock[py][px].second,pblock);
				}

			}

		}

	}


	if (stepandblock.back().back().first != INT_MAX && stepandblock.back().back().second != INT_MAX)
		cout << stepandblock.back().back().first + 1 << endl;
	else
		cout << -1 << endl;


	return 0;
}