[백준 / BOJ] 30024번 : 옥수수밭 - JAVA

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

30024번: 옥수수밭

문제 조건

이 문제는 조건이 아주 단순해서 깊게 구현할 필요가 없었다. '현재 접근할 수 있는 옥수수 중 가장 가치가 높은 것'만 확인하면 된다. 이에 따라 제일 처음 2차원 map 배열을 받으면서 가장자리에 있는 옥수수들의 값을 우선순위 큐에 넣었다.

 

PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {

    @Override
    public int compare(int[] o1, int[] o2) {
        int n = Integer.compare(o2[0], o1[0]);
        return n;
    }

});

boolean[][] v = new boolean[N][M];
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
        if(i == 0 || j == 0 || i == N - 1 || j == M - 1) {
            que.offer(new int[] {map[i][j], i, j});
            v[i][j] = true;
        }
    }
}

 

PriorityQueue의 우선순위 기준

여기서 중요한 건 PriorityQueue에 옥수수의 가치와 위치를 모두 넣어주어야 하기 때문에(그래야 나중에 사방 탐색을 할 수 있다) 1차원 int 배열의 우선순위 기준을 정해야 한다. 값이 클수록 좋기 때문에 Integer.compare(o2[0], o1[0]) 값을 리턴하도록 했다. o2를 먼저 두면 큰 값을 우선하고, o1을 먼저 두면 작은 값을 우선하게 된다.

 

이후에는 가장 큰 값을 poll하고, 해당하는 위치에서 사방탐색을 진행하여 문제를 풀 수 있었다.

 

전체 코드

// 시간 : 756ms
// 메모리 : 131884KB
public class Main {

	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[][] map = new int[N][M];
		
		PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				int n = Integer.compare(o2[0], o1[0]);
				return n;
			}
			
		});
		
		boolean[][] v = new boolean[N][M];
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(i == 0 || j == 0 || i == N - 1 || j == M - 1) {
					que.offer(new int[] {map[i][j], i, j});
					v[i][j] = true;
				}
			}
		}
		
		int K = Integer.parseInt(br.readLine());
		
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		
		StringBuilder sb = new StringBuilder();
		while(K > 0) {
			int[] cur = que.poll();
			int r = cur[1];
			int c = cur[2];
			K--;
			sb.append(r + 1).append(" ").append(c + 1).append("\n");
			
			for (int d = 0; d < 4; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];
				if(nr >= N || nc >= M || nr < 0 || nc < 0) continue;
				if(v[nr][nc]) continue;
				v[nr][nc] = true;
				que.offer(new int[] {map[nr][nc], nr, nc});
			}
			
		}
		
		System.out.print(sb);
	}

}