글 읽기 - 고수님들 부탁드립니다... 반례는 찾았는데 어떻게 해결해야 할까요...?

skatn3 3년 전 0

반례는 다른분이 도움 주셔서 찾았는데 도저히 어느 부분이 잘못되었는 지 모르겠습니다 ㅠㅠ

혹시 도움 주실 수 있으신가요??

6시간동안 이것만 했는데 도저히 못풀겠네요 ..ㅠㅠ 초보자라 코드가 지저분해 죄송합니다.

반례입니다.

7 8 1000
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
0 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
-1 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

제거 답은 :51

정답 : 50

입니다.

import sys
from collections import deque
R,C,T = map(int,input().split())
array = [list(map(int,input().split())) for i in range(R)]
# 공기청정기 좌표
air = [] # 첫번째꺼 윗놈, 두번쨰꺼 아랫놈
for i in range(R):
    if array[i][0] == -1:
        air.append([i,0])

dx = [-1,1,0,0]
dy = [0,0,-1,1]



def bfs():
    q = deque([])
    new_array = [[0]*C for _ in range(R)]

    # 처음에 확산 가능한 곳 전부 queue 에 삽입
    for i in range(R):
        for j in range(C):
            if array[i][j] >0:
                q.append([i,j,array[i][j]]) # 좌표랑 미세먼지 양 삽입

    while q: # 큐에 있는 수 만큼 확산
        x,y,quant = q.popleft() # x,y, 미세먼지 양
        cnt = 0 # 카운팅
        for i in range(4): # 4가지 방향 가능
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >=0 and nx <R and ny>=0 and ny<C: # 범위 안에 들면
                if array[nx][ny] != -1:
                    #print(air[0],nx,ny,end= ' ' )

                    new_array[nx][ny] +=  (quant //5)
                    cnt +=1

        # cnt 개수 다 세었으면
        array[x][y] -= cnt*(quant//5)
    
    # 확산 끝
    for i in range(R):
        for j in range(C):
            array[i][j] += new_array[i][j]


def air_work():
    # 바로 위 잡아먹기
    array[air[0][0]-1][air[0][1]] = 0
    # 바로 아래 잡아먹기
    array[air[1][0]+1][air[0][1]] = 0
    
    # 위 -> 아래
    for i in range(air[0][0]-1):
        array[i+1][0] = array[i][0]
    
    # 아래 -> 위
    for i in range(air[1][0]+1,R-1):
        array[i][0]=array[i+1][0] 


    # 위 => 오른에서 왼, 아래 => 오른에서 왼
    for i in range(C-1):
        array[0][i] = array[0][i+1]
        array[R-1][i] = array[R-1][i+1]

    # 끝에 열 위, 위로 가는거 처리
    for i in range(air[0][0]):
        array[i][C-1] = array[i+1][C-1]

    # 끝에 열 아래, 아래로 가는 거 처리
    for i in range(R-1,air[1][0],-1):
        array[i][C-1] = array[i-1][C-1]

    # 왼쪽에서 오른쪽 밀기
    for i in range(C-1,1,-1):
        array[air[0][0]][i]=array[air[0][0]][i-1]
        array[air[1][0]][i]=array[air[1][0]][i-1]
    
    # 공기청정기 나오는 곳은 0이 되어야함
    array[air[0][0]][1] = 0 
    array[air[1][0]][1] = 0
    
def check():
    result = 0
    for i in range(R):
        for j in range(C):
            if array[i][j] >0 :    
                result+=array[i][j]
    return result

for i in range(T):    
    bfs() # 확산
    air_work()


print(check())
print(array)

            

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

문제

문제

출처

ICPC

고수님들 부탁드립니다... 반례는 찾았는데 어떻게 해결해야 할까요...?

skatn3 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말