글 읽기 - 파이썬 시간초과... 멋쟁이토마토가 되고싶어요...

kc0275 5년 전 0

안녕하세요 자꾸만 시간초과가 떠서 답답한 마음에 질문을 올립니다.

제가 생각한 방법은

시작할 때 1로 시작하는 것들의 좌표를 저장
1에서 저장한 좌표들로 BFS 를 돌리며 인접토마토에 1을 더해 level 을 저장
최종 인접행렬을 검사하며 최대 level - 1 을 프린트

입니다.

이중 for 문이 많이 사용되기는 하는데, 인접행렬로 밖에 풀 수 없는 문제이기 때문에 불가피한 부분이라고 생각했습니다...

어떤 부분을 고쳐야 시간초과 문제를 해결 할 수 있을까요....

많은 도움 부탁드립니다...ㅠ

import sys
import collections

############## 입력받기 ##############

m, n = map(int, sys.stdin.readline().split())
a = [[0]*m for x in range(n)]

one = 0 # 1의 수를 저장 (처음 입력값이 모두 1인 경우 체크하기 위해)
start_point = [] # 1인 좌표를 저장 (bfs 의 시작점을 알기 위해)
for i in range(n):
    temp = sys.stdin.readline().split()
    for j in range(m):
        a[i][j] = int(temp[j])
        if a[i][j] == 1:
            start_point.append((i,j))
            one = one + 1

############## 구현함수 ##############            
            
def isInRange(x,y):
    return (0 <= x and x < n) and (0 <= y and y < m)

def bfs(start_x,start_y):
    queue = collections.deque([])
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    queue.append((start_x,start_y))
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(0,4):
            ax = x + dx[i]
            ay = y + dy[i]
                   
            if isInRange(ax,ay) and a[ax][ay] != 1:
                if a[ax][ay] == 0 or (a[ax][ay] > 0 and a[ax][ay] > a[x][y] + 1):
                    # 이미 bfs 를 한 레벨보다 작은 레벨로 익힐 수 있는 경우 작은 레벨로 변경
                    a[ax][ay] = a[x][y] + 1 
                    queue.append((ax,ay))             

# 최종 행렬을 검사하며 안익었는지 / 최대값이 무엇인지 알려주는 함수
def checkAll(date):
    for i in range(n):
        for j in range(m):
            if a[i][j] == 0:
                return False
            elif date < a[i][j]:
                date = a[i][j]
    return date

############## main ##############

date = 0
if one == n*m:
    date = 0
elif one == 0:
    pass
else:
    for start in start_point:
        bfs(start[0],start[1])
        
    checked = checkAll(date)
    if checked != False:
        date = checked - 1
    else:
        date = -1
        
print(date)

djm03178 5년 전 0

정확하게 이런 코드를 저격하는 데이터를 제가 https://www.acmicpc.net/board/... 에 만들었습니다.

토마토 하나당 전체를 탐색하러 들어가면 안 되고, 모든 토마토로부터 동시에 시작해야 합니다.

kc0275 5년 전 0

정말 감사합니다....ㅠ

동시에 시작하는것은 생각하지 못했는데 그런 방법이 있었네요...

덕분에 맞았습니다...ㅠ 3차원 토마토도 얼른 수정해서 토마토 마스터가 되어야 겠어요!

정말 감사합니다!!! 행복한 연말되세요!!!

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

문제

문제

출처

ICPC

파이썬 시간초과... 멋쟁이토마토가 되고싶어요...

kc0275 5년 전 0

djm03178 5년 전 0

kc0275 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말