[파이썬]백준 1012 유기농배추

링크

백준 1012 유기농배추

간만에 푼 bfs문제, 여태 많이 풀었던 스타일들이랑 비슷했다. 영역의 갯수를 구해주면 된다.

배추의 위치를 1로 처리해주면서 동시에 해당 리스트에서 방문처리는 2로 표시해주어 visit list를 만드는 메모리를 아끼도록 설계했다.

정답 코드

import sys; input = sys.stdin.readline
from collections import deque

def bfs(r, c):
    q = deque()
    q.append([r, c])
    while q:
        r, c = q.popleft()
        arr[r][c] = 2
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < H and 0 <= nc < W:
                if arr[nr][nc] == 1:
                    arr[nr][nc] = 2
                    q.append([nr, nc])

for tc in range(int(input())):

    W, H, K = map(int, input().split())
    start = []
    arr = [([0] * W) for _ in range(H)]
    ans = 0
    for _ in range(K):
        C, R = map(int, input().split())
        start.append((R, C))
        arr[R][C] = 1

    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]

    for cabbage in start:
        r, c = cabbage
        if arr[r][c] == 1:
            bfs(r, c)
            ans += 1

    print(ans)

알게된 것👨‍💻

• 메모리를 아끼자