[BOJ/Gold 4] 백준 30024 옥수수밭(C++)

문제 링크

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

30024번: 옥수수밭

 

문제

옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 N행 M열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 옥수수의 가치를 측정해서 서로 다른 정수 1, 2, ⋯, N × M을 부여했다.

 

 

민석이는 처음에 옥수수밭 바깥에 위치한다. 민석이는 옥수수밭 바깥을 돌아다니면서 옥수수밭 바깥과 인접한 칸의 옥수수를 수확할 수 있다. 또는 옥수수밭 안에서 옥수수를 수확한 칸으로만 돌아다니면서 현재 위치한 칸에서 상하좌우로 인접한 칸의 옥수수를 수확할 수 있다.

그런데, 민석이는 옥수수의 생산량 조절을 위해서 K그루의 옥수수만 수확하려고 한다. 민석이는 현재 수확할 수 있는 옥수수 중에서 가장 가치가 높은 옥수수를 수확하는 과정을 K번 반복한다. 민석이가 수확하는 옥수수의 위치를 순서대로 구해보자.

 

입력

첫째 줄에 정수 N, M(1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 M개의 정수가 공백으로 구분되어 주어진다. N개의 줄 중 i번째 줄의 j번째 정수는 격자에서 i번째 줄의 j번째 칸의 옥수수의 가치를 의미하는 정수 aij(1 ≤ aij ≤ N × M)다.

마지막 줄에 정수 K(1 ≤ K ≤ min(N × M, 100,000))가 주어진다.

 

출력

 K개의 줄에 민석이가 수확하는 옥수수의 위치 i, j(1 ≤ i ≤ N;1 ≤ j ≤ M)를 순서대로 출력한다. i, j는 격자의 i번째 행, j번째 열을 의미한다.

 

예제 입력 1

4 5
1 18 2 3 4
12 17 15 20 5
11 14 19 13 6
10 9 16 8 7
6

예제 출력 1

1 2
2 2
4 3
3 3
2 3
2 4

예제 입력 2

3 3
9 8 1
4 5 2
6 3 7
4

예제 출력 2

1 1
1 2
3 3
3 1

 

알고리즘 분류

• 그래프 탐색
• 자료 구조

 

풀이

먼저 가장자리에 있는 옥수수들만을 우선순위 큐에 담는다. 이 때 우선순위 큐의 우선순위는 옥수수의 가치이다.

우선순위 큐의 top에 위치하는 옥수수를 pop한다. 그리고 수확한 옥수수의 상하좌우에 있는 옥수수를 우선순위 큐에 push하는데, 이 때 이미 수확한 옥수수거나 우선순위 큐에 들어간 옥수수라면 무시한다.

이것을 K번 반복하고 수확한 옥수수의 좌표를 수확한 순서대로 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, K;
int MAP[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
bool Visited[MAX][MAX];
priority_queue<pair<int, pair<int, int> > > PQ;
vector<pair<int, int> > Answer;

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
            if ((i == 0) || (i == N - 1)) {
                PQ.push(make_pair(MAP[i][j], make_pair(i, j)));
                Visited[i][j] = true;
            }
            else {
                if ((j == 0) || (j == M - 1)) {
                    PQ.push(make_pair(MAP[i][j], make_pair(i, j)));
                    Visited[i][j] = true;
                }
            }
        }
    }
    cin >> K;
}

void settings() {
    while (K--) {
        if (PQ.empty()) {
            break;
        }
        pair<int, pair<int, int> > Top = PQ.top();
        PQ.pop();
        for (int i = 0; i < 4; i++) {
            int NextY = Top.second.first + MoveY[i];
            int NextX = Top.second.second + MoveX[i];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M) && !Visited[NextY][NextX]) {
                PQ.push(make_pair(MAP[NextY][NextX], make_pair(NextY, NextX)));
                Visited[NextY][NextX] = true;
            }
        }
        Answer.push_back(make_pair(Top.second.first + 1, Top.second.second + 1));
    };
}

void find_Answer() {
    for (int i = 0; i < (int)Answer.size(); i++) {
        cout << Answer[i].first << " " << Answer[i].second << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}