[백준 - 골드] 30024. 옥수수밭

이번 주의 문제

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

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

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

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

생각해본 풀이

1. 가장자리 기준으로 BFS를 돌리면, 될 것 같다!
2. 가장 가치가 높은 옥수수 = 우선순위 큐를 써서 해보자

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class Point {
		int r;
		int c;
		int corns;

		Point(int r, int c, int corns) {
			this.r = r;
			this.c = c;
			this.corns = corns;
		}
	}

	static int[] dr = { 0, 0, -1, 1 };
	static int[] dc = { -1, 1, 0, 0 };

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] corns = new int[N + 1][M + 1]; // 옥수수밭

		for (int r = 1; r <= N; r++) {
			st = new StringTokenizer(br.readLine());
			for (int c = 1; c <= M; c++) {
				corns[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		int K = Integer.parseInt(br.readLine()); // 반복하는 횟수 또는 K그루의 옥수수만 수확
		
		PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> b.corns - a.corns); //내림차순 정렬이 필요함

		boolean[][] visit = new boolean[N + 1][M + 1];

		//가장자리 탐색
		for (int r = 1; r <= N; r++) {
			if (!visit[r][1]) {
				visit[r][1] = true;
				pq.add(new Point(r, 1, corns[r][1]));
			}

			if (!visit[r][M]) {
				visit[r][M] = true;
				pq.add(new Point(r, M, corns[r][M]));
			}
		}

		for (int c = 1; c <= M; c++) {
			if (!visit[1][c]) {
				visit[1][c] = true;
				pq.add(new Point(1, c, corns[1][c]));
			}

			if (!visit[N][c]) {
				visit[N][c] = true;
				pq.add(new Point(N, c, corns[N][c]));
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int k = 0; k < K; k++) {
			if(!pq.isEmpty()) {
				Point now = pq.poll();
				sb.append(now.r + " " + now.c + "\n");
				
				for(int d = 0; d < 4; d++) {
					
					int nr = now.r + dr[d];
					int nc = now.c + dc[d];
					
					if(nr < 1 || nr > N || nc < 1 || nc > M) continue;
					
					if(visit[nr][nc]) continue; //방문한 곳이면 빼고
					
					visit[nr][nc] = true;
					
					pq.add(new Point(nr, nc, corns[nr][nc]));
				}
			}
		}
		
		System.out.println(sb);

	}
}

함께 보면 좋은 알고리즘

우선순위 큐

FIFO 구조를 띄는 일반적인 Queue와는 다르게, 우선순위를 가진 원소가 먼저 나온다. 우선 순위 기준은 따로 정렬을 해줄 수 있다.

// 낮은 수가 우선순위를 가짐
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 높은 수가 우선순위를 가짐
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

// 사전 순으로 더 빨리오는 문자열이 우선순위를 가짐
PriorityQueue<String> pq = new PriorityQueue<>();

우선순위 큐는 보통의 Queue와 같은 add, remove, poll 등 메서드들을 사용하면 된다.