글 읽기 - 7576 토마토 시간초과 질문

eunkyunghyun 3년 전 0

코드를 이렇게 작성하고 제출하였는데 시간초과가 뜹니다... 혹시 이거 어떻게 해결해야 하나요?

import queue

m, n = map(int, input().split())
farm = []

for i in range(n):
    farm.append(list(map(int, input().split())))

q = queue.Queue()

count = 0

for i in range(n):
    for j in range(m):
        if farm[i][j] == 1:
            q.put((i, j, 0))
            break

arrow = [(0, 1), (1, 0), (0, -1), (-1, 0)]

while not q.empty():
    x, y, count = q.get()
    for i in range(len(arrow)):
        a = x + arrow[i][0]
        b = y + arrow[i][1]
        if 0 <= a < n and 0 <= b < m:
            if farm[a][b] == 0:
                farm[a][b] = farm[x][y] + 1
                q.put((a, b, count+1))
flag = 0

for i in range(n):
    for j in range(m):
        if farm[i][j] == 0:
            flag = -1
            break

if flag == -1:
    print(-1)
else:
    print(count)

hs9200 3년 전 0

저는 비록 c++언어이지만 시간초과가 날땐 토마토 번호 미리 큐에 다때려넣고

한번만 while문 돌리시면 끝입니다.

아니면 파이썬이어서 그런가?

저가 파이썬을 몰라서 한번만 while문 돌렸는지를 모릅니다.(c린이여서)

아무튼 도움이 됬으면 좋겠습니다.

for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] == 1)
			{
				b++;
				q.push(i);
				q.push(j);
			}
			else
			{
				d[i][j] = INF;
			}
		}






//중간생략











while (!q.empty())
	{
		y = q.front(); q.pop();
		x = q.front(); q.pop();
		for (i = 0; i <= 3; i++)
		{
			ty = y + dy[i];        
			tx = x + dx[i];
			if (ty >= 1 && ty <= n && tx >= 1 && tx <= m && a[ty][tx] != -1 && d[ty][tx] > d[y][x] + 1)
			{
				d[ty][tx] = d[y][x] + 1;
				q.push(ty);
				q.push(tx);
				a[ty][tx] = 2;
			}
		}
	}

hs9200 3년 전 0

그냥 토마토1인 지점 다찾아 놓고 큐에 넣고 bfs 한번만 돌리라는 얘기입니다,

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

문제

문제

출처

ICPC

7576 토마토 시간초과 질문

eunkyunghyun 3년 전 0

hs9200 3년 전 0

hs9200 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말