[백준 1012] 유기농 배추

처음엔 bfs로 접근했다가 자꾸 이상하게 돼서 dfs로 풀었다...
dfs 오랜만에 하니 까먹어서 구글링을 좀 했다.

dfs로 접근하기

import sys
from collections import deque
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
T = int(input())

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

for _ in range(T):
    res=0
    M, N, K = map(int,input().split())
    grid = [[0]*(N) for _ in range(M)]
    chk = [[False]*(N) for _ in range(M)]

    for i in range(K):
        x,y = map(int, input().split())
        grid[x][y] = 1

    for i in range(M):
        for j in range(N):
            if not chk[i][j] and grid[i][j] == 1:
                chk[i][j]=True
                res+=1
                dfs(i,j)
    print(res)

BFS로 접근하기

import sys
from collections import deque

input = sys.stdin.readline
T = int(input())

def is_valid_coord(x,y):
    return 0 <= x < M and 0<=y< N
dx = (0,0,1,-1)
dy = (1,-1,0,0)
def bfs(x,y):
    dq=deque()
    dq.append((x,y))
    while(dq):
        a,b = dq.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if is_valid_coord(nx,ny) and not chk[nx][ny] and grid[nx][ny] == 1:
                chk[nx][ny] = True
                grid[nx][ny]=0 
                dq.append((nx,ny))

for _ in range(T):
    res=0
    M, N, K = map(int,input().split())
    grid = [[0]*(N) for _ in range(M)]
    chk = [[False]*(N) for _ in range(M)]

    for i in range(K):
        x,y = map(int, input().split())
        grid[x][y] = 1

    for i in range(M):
        for j in range(N):
            if not chk[i][j] and grid[i][j] == 1:
                chk[i][j]=True
                res+=1
                bfs(i,j)
    print(res)

속도는 bfs 알고리즘이 더 빠름