[백준] 1012번 유기농 배추 DFS, BFS

DFS (메모리 31484KB)

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline
T = int(input())
    
def dfs(x, y):
    #방문처리
    graph[x][y] = 0
    #상하좌우로 움직이면서 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        #범위에 벗어나는지, 그 자리가 1인지(배추가 있으면서 방문X)
        if 0 <= nx <= N-1 and 0 <= ny <= M-1 and graph[nx][ny] == 1:
            dfs(nx,ny)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for test in range(T):
    M, N, K = map(int, input().split())
    graph = [[0] * M for i in range(N)]
    for i in range(K):
        m, n = map(int, input().split())
        graph[n][m] = 1
    count = 0
    #1인 자리를 발견하면 dfs 수행. dfs가 한번 끝나면 count 올리기
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                dfs(i,j)
                count += 1
    print(count)

 

BFS (메모리 34096KB)

import sys
from collections import deque

input = sys.stdin.readline
T = int(input())
    
def bfs(X, Y):
    queue =deque()
    queue.append((X,Y))
    #방문처리
    graph[X][Y] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= N-1 and 0 <= ny <= M-1 and graph[nx][ny] == 1:
                queue.append((nx,ny))
                graph[nx][ny] = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for test in range(T):
    M, N, K = map(int, input().split())
    graph = [[0] * M for i in range(N)]
    for i in range(K):
        m, n = map(int, input().split())
        graph[n][m] = 1
    count = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                bfs(i,j)
                count += 1
    print(count)

 

BFS가 약간 더 비효율적이다.

 

BFS에서 while문 돌아가면서 다음 루프로 가기 직전에 큐에 넣고 그것을 방문처리하는 것을 꼭 기억하자. while문 안에서 방문처리를 하는 것을 자꾸 까먹는다.