백준 python 1012 유기농 배추

백준 링크:https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

dfs와 bfs 둘다 가능한 문제이다.

dfs 풀이

import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    dx,dy=[0,0,1,-1],[1,-1,0,0]
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if (0 <= nx < N) and (0 <= ny < M):
            if matrix[nx][ny] == 1:
                matrix[nx][ny] -= 1
                dfs(nx,ny)

TC=int(input())
for _ in range(TC):
    M,N,K = map(int,input().split())
    matrix=[[0]*M for _ in range(N)]
    cnt = 0

    for _ in range(K):
        m,n=map(int,input().split())
        matrix[n][m] = 1
    for i in range(N):
        for j in range(M):
            if matrix[i][j] > 0:
                dfs(i,j)
                cnt += 1
    print(cnt)

bfs풀이

from collections import deque

dx,dy=[-1,1,0,0],[0,0,-1,1]
def bfs(x,y):
    q= deque()
    q.append((x,y))
    done[x][y] = 1
    while q:
        xx,yy=q.popleft()
        for _ in range(4):
            nx = xx+dx[_]
            ny = yy+dy[_]

            if (0<=nx<n) and (0<=ny<m) and done[nx][ny] == -1:
                if matrix[nx][ny] == 1:
                    q.append((nx,ny))
                    done[nx][ny] = 1
t = int(input())
for __ in range(t):
    cnt = 0
    n,m,k=map(int,input().split())
    matrix=[[0]*m for _ in range(n)]
    done = [[-1]*m for _ in range(n)]

    for _ in range(k):
        a,b=map(int,input().split())
        matrix[a][b] = 1

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1 and done[i][j] == -1:
                bfs(i,j)
                cnt +=1
    print(cnt)

dfs,bfs의 기본 그런데 이렇게 배열을 만들면 메모리가 너무많이 사용하므로 다른 방법을 추천..