컴퓨터 사이언스/1고리즘
백준 1012 : 유기농 배추 (Python)
저세상 개발자
2021. 9. 25. 00:05
https://www.acmicpc.net/problem/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 |