글 읽기 - [python3] 예시들은 잘 돌아가는 것 같습니다만 틀렸다고 나옵니다

ttppggnnss 4년 전 0

혹시 제가 어느 부분에서 실수가 있었는지 봐주시면 감사하겠습니다.

시간초과가 계속 나서 시간을 줄여보려고 노력했는데

어떻게 더 줄일 수 있을지도 말씀해주시면 감사하겠습니다.

또 python3 에서 돌리는 것과 pypy3 에서 돌리는 것에 어떤 차이가 있는지 설명해주시면 감사하겠습니다

import sys
from collections import deque
input=sys.stdin.readline

# 4방위에 바다인 부분 체크
def cnt0(i,j):
    cnt=0
    if L[i+1][j]<1 and r[i+1][j]<1:
            cnt+=1
    if L[i-1][j]<1 and r[i-1][j]<1:
            cnt+=1
    if L[i][j+1]<1 and r[i][j+1]<1:
            cnt+=1
    if L[i][j-1]<1 and r[i][j-1]<1:
            cnt+=1
    return cnt

n,m=map(int,input().split())
L=[[*map(int,input().split())] for _ in 'a'*n]
k=0
q=deque() # 빙산 부분 좌표를 받습니다
for i in range(n):
    for j in range(m):
        if L[i][j]>0:
            q.append((i,j))
            k+=1
time=0
while 1:
    time+=1
    r=[[0]*m for _ in'a'*n] # visited 와 같은 역할을 합니다
    for b in range(k):
        i,j=q.popleft() # q에서 제거했다가
        L[i][j]-=cnt0(i,j)
        if L[i][j]<1:
            r[i][j]=1
        else:
            q.append((i,j)) # 0보다 크면 다시 q에 추가해줍니다
    if k!=len(q): # k값이 변하지 않는다면 덩어리에 변화가 없으므로 넘어갑니다
        k=len(q) # 변했다면 k에 남아있는 빙산 갯수를 넣어줍니다
        if k:
            p=[q[0]]
            k2=0 # 아무 빙산에서 시작해서 덩어리 크기를 구합니다
            while p:
                i,j=p.pop()
                r[i][j]=1
                k2+=1
                if L[i+1][j]>0 and r[i+1][j]<1:
                    p.append((i+1,j))
                if L[i-1][j]>0 and r[i-1][j]<1:
                    p.append((i-1,j))
                if L[i][j+1]>0 and r[i][j+1]<1:
                    p.append((i,j+1))
                if L[i][j-1]>0 and r[i][j-1]<1:
                    p.append((i,j-1))
            if k>k2: # 빙산 크기와 덩어리 크기가 다르면 덩어리가 분리된 것입니다
                print(time)
                break
        else: # k가 0이면 두덩이가 될 수 없습니다
            print(0)
            break

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

문제

문제

출처

ICPC

[python3] 예시들은 잘 돌아가는 것 같습니다만 틀렸다고 나옵니다

ttppggnnss 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말