백준 1012: 유기농 배추 (Python) - bfs/ 런타임 에러 (RecursionError), 시간초과 해결

문제

1012번: 유기농 배추

 

단지번호붙이기 (BOJ2667) 문제와 비슷한 문제이다.

그런데 DFS 재귀로 풀었더니 예제 코드는 정답으로 출력되지만 제출 시 런타임 에러 (RecursionError)가 발생했다.

RecursionError 관련해서는 아래 링크로 확인해보면 발생 이유와 대응 방법에 대해 나온다.

 

런타임 에러 (RecursionError)

 

그래서 재귀방식 대신 큐를 사용해 BFS로 다시 풀었더니 이번엔 시간초과가 나왔다;; (개빡취네)

질문검색 탭을 보니 나랑 똑같은 문제로 틀린 사람이 있었다. (https://www.acmicpc.net/board/view/78364)

다행히 어느 천재님이 아래 내용으로 댓글을 달아주셨다.

 

BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. 
BFS 문제에서 시간 초과나 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.

 

소름돋게 내 코드도 큐에서 뺀 다음에 visit 처리하고 있었다...

존잘님의 방법대로 코드를 수정했더니 바로 정답처리 되었다. (감사합니다..)

 

 

풀이 (Python)

from collections import deque

dx = [1,0,-1,0]
dy = [0,1,0,-1]

if __name__ == '__main__':
    t = int(input())

    for _ in range(t):
        dq = deque()
        m,n,k = map(int, input().split())
        v = [[0]*n for _ in range(m)]
        arr = [[0]*n for _ in range(m)]
        cnt=0

        for _ in range(k):
            a,b = map(int,input().split())
            arr[a][b]=1

        for i in range(m):
            for j in range(n):
                if v[i][j]==0 and arr[i][j]==1:
                    cnt+=1
                    dq.append([i,j])
                    v[i][j]=1
                    while dq:
                        cx, cy = dq.popleft()
                        #v[cx][cy] = 1 <<문제의 기존 visit 처리
                        for k in range(4):
                            nx = cx + dx[k]
                            ny = cy + dy[k]
                            if (0 <= nx < m and 0 <= ny < n and v[nx][ny] == 0 and arr[nx][ny] == 1):
                                dq.append([nx,ny])
                                v[nx][ny]=1
        print(cnt)

 

^ㅇ^