글 읽기 - 빙산 시간초과 질문입니다

nan308 4년 전 0

시간초과가 자꾸 발생하는데 어디에서 문제가 되는지 감이 안와서 질문 올립니다 ㅠ

도와주시면 감사하겠습니다. ㅠㅠ

def chk_fin():
    rs = 0
    for i in bd:
        rs += sum(i)
    if rs == 0:
        return False
    else :
        return True


def all_vis():
    rs = 0
    for i in vis:
        rs += i.count(0)
    if rs == 0:
        return False
    else :
        return True


def rs_vis():
    for x in range(n):
        for y in range(m):
            vis[x][y] = 0


def go(st_x, st_y):
    global l_cnt
    for x in range(st_x, n):
        for y in range(st_y, m):
            if vis[x][y] == 0:
                vis[x][y] = 1
                if bd[x][y] > 0:
                    dq.append([x, y])
                    l_cnt += 1
                    go_set = [x, y]
                    return 0


n, m = map(int, input().split())
bd = []
vis = []
q = []
dq = []
near = [[-1, 0], [0, 1], [1, 0], [0, -1]]
for i in range(n):
    bd.append(list(map(int, input().split())))
    vis.append([0 for i in range(m)])

# 빙산 녹이기
cnt = 0
while chk_fin():
    go_set = [0, 0]
    rs_vis()
    l_cnt = 0
    cnt += 1
    for x in range(n):
        for y in range(m):
            if bd[x][y] == 0:
                if [x, y] not in q:
                    q.append([x, y])
    # 한번 녹임

    while q:
        x, y = q.pop(0)
        for a, b in near:
            if 0 <= x+a < n and 0 <= y+b < m:
                if bd[x+a][y+b] > 0 :
                    bd[x+a][y+b] -= 1
    
    # 빙산 덩어리 찾기 시작
    
    while all_vis():
        go(go_set[0], go_set[1])
        while dq:
            x, y = dq.pop(0)
            for a, b in near:
                if 0 <= x+a < n and 0 <= y+b < m:
                    if vis[x+a][y+b] == 0 :
                        vis[x+a][y+b] = 1
                        if bd[x+a][y+b] > 0:
                            dq.append([x+a, y+b])
    if l_cnt > 1:
        break
    if not chk_fin():
        cnt = 0
        break
print(cnt)
# print(l_cnt)

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

문제

문제

출처

ICPC

빙산 시간초과 질문입니다

nan308 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말