[Python] 백준 1012번 - 유기농 배추

문제: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

자주 접하던 BFS 유형이라 다음과 같이 풀었다.

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    global board
    global visited
    q = deque()
    q.append([x, y])
    
    while q:
        x, y = q.popleft()
        visited[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1 and not visited[nx][ny]:
                q.append([nx, ny])
    
t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    board = [[0]*m for _ in range(n)]
    
    for _ in range(k):
        y, x = map(int, input().split())
        board[x][y] = 1
        
    visited = [[0]*m for _ in range(n)]
    count = 0
    
    for x in range(n):
        for y in range(m):
            if board[x][y] == 1 and not visited[x][y]:
                count += 1
                bfs(x, y)
    print(count)

그런데 계속 메모리 초과 에러가 발생했다.

메모리 제한이 512MB라서 얼마나 쓰고있는지 확인해보고 싶어서 찾아보니까 psutil이라는 모듈을 사용해서 확인해볼 수 있는 것 같다. 

그런데 찾아보니 프로세스에 대한 메모리를 계산해주는 것 같은데 코드가... 이해하려면 배보다 배꼽이 더 큰느낌이 들었다..

코드 보면서 메모리 줄일 수 있는 부분이 있나 보니까, visited를 습관처럼 썼는데, 해당 문제에서는 한번 들렸던 배추 자리를 0 으로 바꿔줌으로써 visited를 대신할 수 있었다.

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    global board
    q = deque()
    q.append([x, y])
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 1:
                q.append([nx, ny])
                board[nx][ny] = 0
    
t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    board = [[0]*m for _ in range(n)]
    
    for _ in range(k):
        y, x = map(int, input().split())
        board[x][y] = 1
        
    count = 0
    
    for x in range(n):
        for y in range(m):
            if board[x][y] == 1:
                count += 1
                bfs(x, y)
    print(count)

따라서 이렇게 코드를 바꾸고 나서 통과!