백준 1012 : 유기농 배추 (Python)

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

1012번: 유기농 배추

 

단순 bfs문제다.

파이썬에 익숙해질 필요가 있어 파이썬으로 풀어봤다.

 

from collections import deque

max_size = 50
board = [[0 for _ in range(max_size)] for _ in range(max_size)]
visited = [[False for _ in range(max_size)] for _ in range(max_size)]

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

def bfs(m, n):
    q = deque()
    ans = 0

    for i in range(n):
        for j in range(m):
        	# 체크되지 않은 새로운 구역 발견
            if not visited[i][j] and board[i][j]:
                q.append((j, i))
                visited[i][j] = 1
                ans += 1

                while q:
                    x, y = q.popleft()

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]

                        if (nx < 0 or ny < 0 or nx >= m or ny >= n or visited[ny][nx] or not board[ny][nx]): 
                            continue

                        visited[ny][nx] = 1
                        q.append((nx, ny))
    return ans


def solution():
    t = int(input())

    while t:
        m, n, k = list(map(int, input().split()))

		# 리스트 초기화
        for i in range(n):
            for j in range(m):
                board[i][j] = 0
                visited[i][j] = False

		# 무 심기 배추인가?
        for _ in range(k):
            x, y = list(map(int,input().split()))
            board[y][x] = 1
        
        print(bfs(m, n))
        t -= 1

# main
solution()

# 내일 시험 잘 치게 해주세요.

Python3

메모리: 32140 kb

시간: 372 ms

PyPy3

메모리: 130248 kb

시간: 228 ms