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

문제 링크

https://www.acmicpc.net/problem/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

 

알고리즘 분류

• 그래프 탐색
• 자료 구조

 

풀이

가장 먼저, 가장자리(0, N-1번째 행과 열)에 있는 모든 옥수수만을 수확할 수 있다.

근데 해당 옥수수를 수확했다고 해서, 반드시 그 다음 상하좌우에 위치하는 옥수수들을 수확해야 하는 것은 아니고 그 다음 가치가 높은 옥수수를 수확할 수도 있다.

무조건 가장 높은 가치를 가진 옥수수만을 수확하면 되는 것이므로 우선순위 큐를 이용한다.

가장자리에 있는 모든 옥수수들을 우선순위 큐에 추가하는데, 이 때 반드시 최대 힙을 이용해서 가치가 높은 옥수수가 Top에 있게 한다.

Top, 그러니까 가장 가치가 높은 옥수수를 수확한 후, 상하좌우에 위치하는, 아직 우선순위 큐에 담지 않은 옥수수를 우선순위 큐에 담는다.

그리고 그 다음 가치가 높은 옥수수를 수확하고, 또 상하좌우에 위치하는 옥수수들을 담는다. 이것을 K번 반복하면서, 수확한 옥수수의 좌표를 출력한다.

 

해결 완료 시각

 

코드

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

public class Main {
	
	private static class Info implements Comparable<Info> {
		
		int C, Y, X;
		
		public Info(int C, int Y, int X) {
			super();
			
			this.C = C;
			this.Y = Y;
			this.X = X;
		}
		
		@Override
		public int compareTo(Info o) {
			return (o.C - this.C);
		}
		
	}
	
    private static int N, M, K;
    private static int[][] map = new int[1001][1001];
    private static boolean[][] visited = new boolean[1001][1001];
    private static int[] moveY = { -1,0,1,0 };
    private static int[] moveX = { 0,-1,0,1 };
    private static PriorityQueue<Info> pq = new PriorityQueue<>();
    private static StringBuilder sb = new StringBuilder();
    
    private static void settings() {
    	for (int i = 0; i < K; i++) {
    		Info now = pq.poll();
    		int nowY = now.Y;
    		int nowX = now.X;
    		sb.append((nowY + 1) + " " + (nowX + 1) + "\n");
    		
    		for (int j = 0; j < 4; j++) {
    			int nextY = nowY + moveY[j];
    			int nextX = nowX + moveX[j];
    			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M) && !visited[nextY][nextX]) {
    				visited[nextY][nextX] = true;
    				pq.add(new Info(map[nextY][nextX], nextY, nextX));
    			}
    		}
    	}
    }

    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	String[] inputs = br.readLine().split(" ");
    	N = Integer.parseInt(inputs[0]);
    	M = Integer.parseInt(inputs[1]);
    	
    	for (int i = 0; i < N; i++) {
    		inputs = br.readLine().split(" ");
    		for (int j = 0; j < M; j++) {
    			map[i][j] = Integer.parseInt(inputs[j]);
    			
    			if ((i == 0) || (i == N - 1)) {
    				pq.add(new Info(map[i][j], i, j));
    				visited[i][j] = true; 
    			} else {
    				if ((j == 0) || (j == M - 1)) {
    					pq.add(new Info(map[i][j], i, j));
    					visited[i][j] = true; 
    				}
    			}
    		}
    	}
    	
    	K = Integer.parseInt(br.readLine());
    	
    	settings();
    	
    	bw.write(sb.toString());
    	bw.close();
    	br.close();
    }

}