글 읽기 - [파이썬] 시간 초과

dhdudwn95 2년 전 0

while True:

빙산의 조각수 확인(BFS/DFS) > 조각수가 2개 이상이라면 while문 break > 조각수가 하나라면 melt

모양으로 하고 있는데.. 어떻게 메모리랑 시간을 줄여야할지 감이 안옴니다.. 도와주십쇼ㅠ

(1번 풀이와 2번 풀이의 차이점은 빙산의 조각수를 확인하는 메소드가 DFS/BFS차이 뿐입니다)

# 풀이 1 : DFS

from copy import deepcopy
import sys

sys.setrecursionlimit(10**7)

def melt(graph, visited):
    count = 0
    if graph[x][y] !=0:
        visited[x][y] = True
        for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx = x + dx
            ny = y + dy
            if 0<=nx<row and 0<=ny<col:
                if graph[nx][ny]==0 and visited[nx][ny] == False:
                    count +=1
        if graph[x][y] < count:
            graph[x][y] = 0
        else:
            graph[x][y] -= count
        

def check_if(graph, x, y):

    if graph[x][y]!=0:
        graph[x][y] =0
        for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx = x + dx
            ny = y + dy
            if 0<=nx<row and 0<=ny<col:
                check_if(graph, nx, ny)
        return True
    return False

row, col = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split()))for  _ in range(row)]

round = 0
while True:
    answer = 0
    copy_graph = deepcopy(graph)
    for x in range(1,row-1):
        for y in range(1,col-1):
            if check_if(copy_graph, x, y):
                answer +=1
    if answer >1:
        break

    visited = [[False]*col for _ in range(row)]
    for x in range(1,row-1):
        for y in range(1, col-1):
            if graph[x][y] !=0:
                melt(graph, visited)
    round +=1

print(round)

# 풀이 2: BFS

from copy import deepcopy
from collections import deque
import sys

sys.setrecursionlimit(10**7)

def melt(graph, visited):
    count = 0
    if graph[x][y] !=0:
        visited[x][y] = True
        for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx = x + dx
            ny = y + dy
            if 0<=nx<row and 0<=ny<col:
                if graph[nx][ny]==0 and visited[nx][ny] == False:
                    count +=1
        if graph[x][y] < count:
            graph[x][y] = 0
        else:
            graph[x][y] -= count
        
def BFS(graph, a, b):
    q = deque()
    q.append([a, b])
    graph[a][b] = 0
    while q:
        x, y = q.popleft()
        for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            nx = x + dx
            ny = y + dy
            if 0<=nx<row and 0<=ny<col:
                if graph[nx][ny] !=0:
                    graph[nx][ny] = 0
                    q.append([nx,ny])

row, col = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split()))for  _ in range(row)]

round = 0
while True:
    answer = 0
    copy_graph = deepcopy(graph)
    for x in range(1,row-1):
        for y in range(1,col-1):
            if copy_graph[x][y] !=0:
                BFS(copy_graph, x, y)
                answer +=1
    if answer >1:
        break

    visited = [[False]*col for _ in range(row)]
    for x in range(1,row-1):
        for y in range(1, col-1):
            if visited[x][y] == False:
                melt(graph, visited)
    round +=1

print(round)

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

문제

문제

출처

ICPC

[파이썬] 시간 초과

dhdudwn95 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말