Baekjoon 1012.py [유기농 배추]

내 풀이

import sys
from collections import deque


input = sys.stdin.readline
dx, dy = [1, -1, 0, 0], [0, 0, -1, 1]


def bfs(x, y):
    queue = deque([[x, y]])
    arr[x][y] = 0
    while queue:
        v = queue.popleft()
        vx, vy = v[0], v[1]
        for i in range(4):
            xx = vx + dx[i]
            yy = vy + dy[i]
            if 0 <= xx < n and 0 <= yy < m and arr[xx][yy] == 1:
                arr[xx][yy] = 0
                queue.append([xx, yy])


t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    arr = [[0]*m for _ in range(n)]
    cnt = 0
    for _ in range(k):
        y, x = map(int, input().split())
        arr[x][y] = 1
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

풀이 복기

방향벡터를 설정하지않고 모든 경우를 if 문으로 작성하려 했다. 방향벡터를 잘 활용해서 문제 풀자.
pop(0)보다 시간복잡도가 적은 popleft()를 잘 활용하자.
DFS, BFS문제가 나온다고해서 바로 visted리스트를 만들어 쓰려하지 말자. 기존 리스트를 활용할수있으면 최대한 활용하는게 더 좋은 풀이라 생각함.