[C++/30024] 옥수수 밭

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

애증의 BFS 입니다. 이 유형 문제를 예전에는 엄청 많이 풀었었습니다. 각설하고, 간략하게 문제를 요약해보겠습니다. 이 문제는 각 칸에 옥수수가 심어져 있는데, 옥수수의 가치가 1 부터 n * m 만큼 격자에 부여를 했습니다.

그래서 민석이는 옥수수 밭 바깥을 돌아다니며, 인접한 칸에서 옥수수를 수확할 수 있는데 한정된 K그루의 개수만 획득을 할 수 있습니다. 항상 이런문제는 최고의 가치를 원합니다. 그래서 매번 최고의 옥수수를 수확해야합니다.

그래서, 이 문제는 일단 민석이는 바깥에 있는 모든 옥수수에 접근이 가능하니 바깥에 있는 옥수수를 전부 우선순위 큐에 집어 넣습니다. 그 이유는 우선순위 큐안에서 자동으로 정렬이 되기 때문에 먹을 수 있는 최고의 옥수수를 먹을 수 있기 때문입니다.

그리고 이를 이용해서 BFS를 돌려주면 방문할 수 있는 옥수수를 우선순위큐에 삽입하면서 최고의 옥수수를 K개 먹을 수 있을 것입니다. 해당 문제를 풀때 오랜만에 풀어서 visited 이차원 배열에 체크를 제대로 하지 않아서 두번정도 틀렸는데, 항상 BFS 문제를 해결할 때는 방문처리가 중요하다는것을 매번 생각합니다.

아래는 정답 코드입니다.

#include<iostream>
#include<cstring>
#include<queue>

#define MAX 1010
using namespace std;

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

vector<pair<int,int> > answer;
int n,m,k,board[MAX][MAX],visited[MAX][MAX];

struct info{
	int score;
	int y;
	int x;
};

struct compare{
	bool operator()(const info a, const info b){
		return a.score < b.score;
	}
};

priority_queue< info, vector<info>, compare> pq;

void init(){
	
	memset(visited,false,sizeof(visited));
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
			if(i == 0 || j == 0 || i == n - 1 || j == m - 1) {
				visited[i][j] = 1;
				pq.push({board[i][j],i,j});
			}
		}	
	}
	
	cin >> k;
}

int isRange(int y, int x){
	return 0 <= y && y < n && 0 <= x && x < m;
}

int main(){
	
	init();
	
	while(k--){
		
		if(pq.empty()) break;
		int y = pq.top().y;
		int x = pq.top().x;
		int score = pq.top().score;
		pq.pop();

		answer.push_back({y,x});
		
		for(int i = 0; i < 4; i++){
			
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(!isRange(ny,nx)) continue;
			if(visited[ny][nx]) continue;
			
			visited[ny][nx] = 1;
			pq.push({board[ny][nx],ny,nx});
		}
		
	}
	
	for(int i = 0; i < answer.size(); i++){
		cout << answer[i].first + 1 << " " << answer[i].second + 1 << "\n";
	}

}