백준 1600 c++ "말이 되고픈 원숭이" -[PlusUltraCode]

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

1600번: 말이 되고픈 원숭이

[필자 사고]

BFS() 탐색 문제이다.

 

이 문제의 특이한 점은 말의 능력을 사용할 수 있다는 점이다. 처음 필자는 문제를 풀 때

 

visted를 2차원 배열로 구현하고 문제를 풀었지만 우선순위큐가 너무 과도하게 많이 만들어진 결과

 

메모리 초과의 문제를 만들어냈다. 

 

핵심은 visted를 3차원 배열로 구현해 우선순위 큐가 과도하게 만들어지는걸 방지해야 된다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int M, N;

typedef struct Node {
	int mal;
	int count;
	int sero;
	int garo;
}Node;
struct cmp {
	bool operator()(Node a, Node b) {
		return a.count > b.count;
	}
};


int dx_mal[8] = { 2,1,-1,-2,-2,-1,1,2 };
int dy_mal[8] = { 1,2,2,1,-1,-2,-2,-1 };

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int K;
vector<vector<int>> Arr;
bool visited[31][201][201];

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M) {
		return true;
	}
	return false;
}



void Input() {
	cin >> K;
	cin >> M >> N;
	Arr.resize(N);

	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
		
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> Arr[i][k];
		}
	}
}

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

				}
			}
		}
		
			for (int i = 0; i < 4; i++) {
				int nextSero = nowSero + dy[i];
				int nextGaro = nowGaro + dx[i];
				if (Inside(nextSero, nextGaro) &&
					Arr[nextSero][nextGaro] == 0 &&
					visited[nowK][nextSero][nextGaro] == false) {
					pq.push({ nowK ,nowCount + 1,nextSero,nextGaro });
				
				}
			}
		
	}
	cout << -1;
	return;
}

void Print() {
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (visited[i][k])cout << 1 << " ";
			else cout << 0 << " ";
		}
		cout << '\n';
	}
}

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

	
}