백준 14442 c++ "벽 부수고 이동하기 2" -[PlusUltraCode]

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

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

 

[필자 사고]

이 문제는 BFS업그레이드 문제이다.

 

이 문제를 풀기 시작했따면 장애물이 있을 때 BFS탐색 문제를 많이들 풀어 봤을 것이다.

 

장애물 BFS에 더불어서 visited[][][] 3차원으로 작성하여 벽을 부술 수 있는 능력까지 체크해주면 쉽게 풀 수 있다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int N, M, K;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
typedef struct Node {
	int sero;
	int garo;
	int count;
	int skill;
}Node;
struct cmp {
	bool operator()(Node a, Node b) {
		return a.count > b.count;
	}
};
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}


bool visited[11][1001][1001];
vector<vector<int>> Arr;



void Input() {
	cin >> N >> M >> K;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
	}
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			Arr[i][k] = str[k] - '0';
		}
	}
}

void BFS() {
	priority_queue<Node, vector<Node>, cmp> pq;
	pq.push({ 0,0,1,K });
	while (!pq.empty()) {
		int nowSero = pq.top().sero;
		int nowGaro = pq.top().garo;
		int nowCount = pq.top().count;
		int nowSkill = pq.top().skill;
		pq.pop();
		if (nowSero == N - 1 && nowGaro == M - 1) {
			cout << nowCount;
			return;
		}
		if (visited[nowSkill][nowSero][nowGaro] == true)continue;
		visited[nowSkill][nowSero][nowGaro] = true;
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (nowSkill > 0) {
				if (Inside(nextSero, nextGaro) == true) {
					if (Arr[nextSero][nextGaro] == 1) {
						if (visited[nowSkill - 1][nextSero][nextGaro] == false) {
							pq.push({ nextSero,nextGaro,nowCount + 1,nowSkill - 1 });
						}
					}
					else {
						if (visited[nowSkill][nextSero][nextGaro] == false) {
							pq.push({ nextSero,nextGaro,nowCount + 1,nowSkill  });
						}
					}
				}
				
			}
			else if (nowSkill == 0) {
				if (Inside(nextSero, nextGaro) &&
					Arr[nextSero][nextGaro] == 0 &&
					visited[nowSkill][nextSero][nextGaro] == false) {
					pq.push({ nextSero,nextGaro,nowCount + 1,nowSkill });
				}
			}
			
		}
	}
	cout << -1;
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	BFS();
}