글 읽기 - 유기 농배추 문제 dfs는 맞았는데 bfs는 시간 초과가 나옵니다...

david02324 3년 전 0

farm이중 리스트에 배추 있는지 없는지 bool값으로 저장하고 bfs로 작성하고 제출했는데 시간 초과가 나옵니다 ㅠㅠ pypy로 제출하니 메모리 초과가 나오네요.. 뭐가 문제일까요..?

import sys
from collections import deque
input = sys.stdin.readline

def findArea(M,N,K):
    farm = [[False]*M for _ in range(N)]
    for _ in range(K):
        X,Y = map(int,input().split())
        farm[Y][X] = True

    areaCount = 0
    queue = deque()
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    for y in range(N):
        for x in range(M):
            if farm[y][x]:
                areaCount += 1
                queue.append((x,y))
                while queue:
                    coord = queue.popleft()
                    tx = coord[0]
                    ty = coord[1]
                    farm[ty][tx] = False

                    for i in range(4):
                        newX = tx + dx[i]
                        newY = ty + dy[i]
                        if 0 < newX < M and 0 < newY < N and farm[newY][newX]:
                            queue.append((newX,newY))
                        
    return areaCount

for _ in range(int(input())):
    M,N,K = map(int,input().split())
    print(findArea(M,N,K))

shg9411 3년 전 1

큐에서 뽑고 나서가 아니라 넣을 때 처리해주세요.

david02324 3년 전 0

헐.. False로 바꾸는걸 위치만 바꾸니까 통과했습니다... 혹시 왜그런건가요???? 뽑고나서 바꾸는거랑 넣을떄 바꾸고 넣는거랑 차이가 있나요?

shg9411 3년 전 0

큐에서 꺼낼 때 체크하시면 동일한 좌표가 큐에 또 삽입이 될 수 있습니다.

david02324 3년 전 0

아...생각해보니 맞네요... 답변 감사드립니다!!

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

문제

문제

출처

ICPC

유기 농배추 문제 dfs는 맞았는데 bfs는 시간 초과가 나옵니다...

david02324 3년 전 0

shg9411 3년 전 1

david02324 3년 전 0

shg9411 3년 전 0

david02324 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말