[Gold IV] 옥수수밭 - 30024

문제 링크

성능 요약

메모리: 156344 KB, 시간: 816 ms

분류

자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 우선순위 큐

제출 일자

2025년 6월 9일 14:01:05

문제 설명

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

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

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

입력

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

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

마지막 줄에 정수 $K(1\le K \le \min(N \times M, 100\,000))$가 주어진다.

출력

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

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/30024
 
from sys import stdin
input = stdin.readline
 
import heapq
 
n, m = map(int, input().split())
 
place = [list(map(int, input().split())) for x in range(n)]
k  = int(input())
 
 
 
outheap = []
 
 
for y in range(0, n):
    for x in range(0, m):
        if y == 0 or y == n -1 or x == 0 or x == m - 1:
            heapq.heappush(outheap, (-place[y][x], y, x))
 
directions = [(-1 , 0), (+1 , 0), (0 , -1) , (0 , + 1)]
 
def outline(k):
    for t in range(k):
        while True:
            negval, y, x = heapq.heappop(outheap)
            val = -negval
            #초기값
            # if val != 0:
            if place[y][x] != 0:
                break
 
        print(y + 1, x + 1)
        place[y][x] = 0
 
        
        for dy, dx in directions:
            ny, nx = (y + dy,  x + dx)
            if  0 <= ny < n and 0<= nx < m:
                if place[ny][nx] != 0:
                    heapq.heappush(outheap, (-place[ny][nx], ny, nx))
        
    
       
        
 
 
    
outline(k)