글 읽기 - 이 코드의 문제점이 궁금합니다.

(追記) (追記ここまで)

이 코드의 문제점이 궁금합니다.

30024번 - 옥수수밭

sk14cj 1년 전 0

초기 외곽 상태를 저장하는 코드 및 visited 관리를 조금 비효율적이더라도 더 안전하게(?) 관리하는 코드를 작성하여 결국 AC 판정을 받기는 했으나, 처음에 답안으로 제출한 이 코드가 WA 판정을 받는 이유를 잘 모르겠습니다.

import sys, heapq
input = sys.stdin.readline
def main():
 n,m = map(int,input().split())
 graph = [list(map(int,input().split())) for _ in range(n)]
 visited = [[False]*m for _ in range(n)]
 k = int(input())
 q = []
 for i in range(n): #외곽
 visited[i][0], visited[i][m-1] = True, True
 heapq.heappush(q,(-graph[i][0],i,0))
 heapq.heappush(q,(-graph[i][m-1],i,m-1))
 for i in range(1,m-1):#외곽
 visited[0][i], visited[n-1][i] = True, True
 heapq.heappush(q,(-graph[0][i],0,i))
 heapq.heappush(q,(-graph[n-1][i],n-1,i))
 dx = [0,1,0,-1]
 dy = [1,0,-1,0]
 answer = 0
 for _ in range(k):
 tmp, vx, vy = heapq.heappop(q)
 answer -= tmp
 for i in range(4):
 nx = vx + dx[i]
 ny = vy + dy[i]
 if nx < 0 or ny < 0 or nx >= n or ny >= m or visited[nx][ny]: continue
 visited[nx][ny] = True
 heapq.heappush(q,(-graph[nx][ny],nx,ny))
 print(vx+1,vy+1)
if __name__ == "__main__":
 main()

crisjan 4달 전 0

이미 해결하신 것 같지만, 저도 같은 오류 때문에 고생을 해서 혹시나 같은 고민하시는 분들이 있을까 해서 남깁니다!

초기에 힙에 외곽 상태 넣을 때, 괜히 이중 for문 안태우려고 저렇게 하면

2 1

같은 케이스에서는 힙에 똑같은 값이 2개씩 들어가게 됩니다! (N, M = 2, 1 -> 0 == M-1)

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC