[백준] 1012 유기농 배추 (실버2) / BFS (방문체크 위치 정확히!)

문제요약

나의 코드 및 설명

• 너비우선탐색(BFS)을 통해 연속된 배추가 심어진 좌표를 모두 0으로 바꾼다.
• 메인 함수 부분의 for문을 통해 배추가 심어진 좌표(1)일 경우 bfs 함수가 호출되게 되고 배추가 심어진 좌표의 값(1)을 0으로 바꿔주고 ans에 1을 더한다.

from collections import deque

def bfs(sx,sy):
    queue = deque()
    queue.append((sx,sy))

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=m or ny>=n:
                continue
            else:
                if board[ny][nx] == 1 and visited[ny][nx] == 0:
                    board[ny][nx] = 0 #배추가 심어진 좌표(1)를 방문하면 (0)으로 바꾼다.
                    visited[ny][nx] = 1
                    queue.append((nx,ny))

t = int(input())
for test_case in range(1, t+1):
    m, n, k = map(int, input().split()) #m:가로 / n:세로 / k:배추 심겨진 위치 개수
    board = [[0]*m for _ in range(n)]

    for _ in range(k):
        x,y = map(int, input().split())
        board[y][x] = 1

    visited = [[0]*m for _ in range(n)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    ans = 0

    for i in range(n):
        for j in range(m):
            if board[i][j] == 1: 
                bfs(j,i) #이어진 배추가 심어진 좌표를 모두 0으로 바꾸게 된다.
                ans += 1 
    
    print(ans)

피드백

BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않는다. 시간 초과가 발생하면 이 점을 지켰는지 의심해봐야 한다고 한다.

BFS는 큐에 넣을 때 방문 체크를 해야 함!!

큐에서 뺀 다음 방문 체크를 하면 중복 방문으로 처리 되어 시간초과 발생!