백준 30024 (옥수수밭) - java

문제

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

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

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

 

유형 : 우선순위 큐

 

접근 방식

• '현재 수확할 수 있는 옥수수 중에서 가장 가치가 높은 옥수수를 수확' 이라는 것에 주의하여 문제를 풀어야 한다.
• 즉 처음에는 가장 외각에 대한 정보를 PQ에 추가한다.
• 그리고 K번의 반복문을 돌리면서 PQ에서 제거한 위치 정보를 결과에 추가하고 4방 탐색을 하여 이전에 추가하지 않은 좌표 정보라면 추가한다.

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int n,m;
    static int k;
    static int[][] board;
    static boolean[][] v;

    static long result = 0;

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

    static PriorityQueue<Point> pq = new PriorityQueue<>(
            (x,y) -> y.v - x.v
    );

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];
        v = new boolean[n+1][m+1];
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 1 ; j <= m ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        k = Integer.parseInt(br.readLine());

        for(int i = 1 ; i <= n ; i++) {
            if(!v[i][1]) {
                v[i][1] = true;
                pq.add(new Point(i, 1, board[i][1]));
            }

            if(!v[i][m]) {
                v[i][m] = true;
                pq.add(new Point(i, m, board[i][m]));
            }
        }

        for(int i = 1 ; i <= m ; i++) {

            if(!v[1][i]) {
                v[1][i] = true;
                pq.add(new Point(1, i, board[1][i]));
            }

            if(!v[n][i]) {
                v[n][i] = true;
                pq.add(new Point(n, i, board[n][i]));
            }
        }

        for(int i = 0 ; i < k ; i++) {
            if(!pq.isEmpty()) {
                Point tmp = pq.poll();
                sb.append(tmp.x+" "+tmp.y+"\n");

                for(int j = 0 ; j < 4 ; j++) {
                    int nx = tmp.x + dx[j];
                    int ny = tmp.y + dy[j];

                    if(nx < 1 || nx > n || ny < 1 || ny > m)
                        continue;

                    if(v[nx][ny])
                        continue;
                    
                    v[nx][ny] = true;

                    pq.add(new Point(nx,ny,board[nx][ny]));
                }
            }
        }

        System.out.println(sb);

        br.close();
    }

    static class Point {
        int x;
        int y;
        int v;

        Point(int x,int y,int v) {
            this.x = x;
            this.y = y;
            this.v = v;
        }
    }
}