글 읽기 - 파이썬 시간초과가 떠요

exon 1년 전 1

1. while 로 덩어리가 0이나 2이상이 될 때까지 반복

a. bfs로 몇개인지

b. 빙산 녹이기

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

def bfs(g, x, y, visited):
    queue = deque([(y, x)])
    visited[y][x] = True
    while queue:
        vy, vx = queue.popleft()
        visited[vy][vx] = True
        if vy < n-2 and not visited[vy+1][vx] and g[vy+1][vx] > 0:
            queue.append((vy+1, vx))
            visited[vy+1][vx] = True
        if vy > 1 and not visited[vy-1][vx] and g[vy-1][vx] > 0:
            queue.append((vy-1, vx))
            visited[vy-1][vx] = True
        if vx < m-2 and not visited[vy][vx+1] and g[vy][vx+1] > 0:
            queue.append((vy, vx+1))
            visited[vy][vx+1] = True
        if vx > 1 and not visited[vy][vx-1] and g[vy][vx-1] > 0:
            queue.append((vy, vx-1))
            visited[vy][vx-1] = True
    return 1

r = 0
while True:
    graph2 = graph[:]
    cnt = 0
    visited = [[False for __ in range(m)] for _ in range(n)]
    for i in range(1, n-1):
        for j in range(1, m-1):
            if graph[i][j] > 0 and not visited[i][j]:
                if bfs(graph, j, i, visited) == 1:
                    cnt += 1

    for i in range(1, n-1):
        for j in range(1, m-1):
                a = 0
                if graph[i+1][j] == 0:
                    a += 1
                if graph[i-1][j] == 0:
                    a += 1
                if graph[i][j+1] == 0:
                    a += 1
                if graph[i][j-1] == 0:
                    a += 1
                graph2[i][j] = 0 if (graph[i][j] - a < 0) else graph[i][j] - a
    graph = graph2[:]
    
    if cnt >= 2 or cnt == 0:
        break
    r += 1
print(r)

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

문제

문제

출처

ICPC

파이썬 시간초과가 떠요

exon 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말