[BOJ] DFS/BFS - 1012 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

[DFS]

 

import sys

# 재귀 제한을 늘려준다.
sys.setrecursionlimit(10**6)

t = int(sys.stdin.readline().rstrip())

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


def dfs(x, y, group_number):
    # 현재 정점은 배추흰지렁이가 보호한다.
    group[x][y] = group_number

    # 인접한 배추들도 배추흰지렁이가 보호한다.
    for i in range(len(dx)):
        nx = x + dx[i]
        ny = y + dy[i]

        if not (0 <= nx < n and 0 <= ny < m):
            continue

        if graph[nx][ny] == 1 and group[nx][ny] == -1:
            dfs(nx, ny, group_number)


for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().rstrip().split())
    graph = [[0] * m for _ in range(n)]
    group = [[-1] * m for _ in range(n)]

    for _ in range(k):
        y, x = map(int, sys.stdin.readline().rstrip().split())
        graph[x][y] = 1

    group_number = 0

    for i in range(n):
        for j in range(m):
            # 배추가 심어져 있고, 배추흰지렁이가 없다면 추가한다.
            if graph[i][j] == 1 and group[i][j] == -1:
                group_number += 1
                dfs(i, j, group_number)

    # 필요한 배추흰지렁이 최소 마리 수
    print(group_number)

 

 

[BFS]

 

import sys
from collections import deque

t = int(sys.stdin.readline().rstrip())

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


def bfs(i, j, group_number):
    # 현재 정점은 배추흰지렁이가 보호한다.
    queue = deque()
    queue.append((i, j))
    group[i][j] = group_number

    while queue:
        x, y = queue.popleft()

        # 인접한 배추들도 배추흰지렁이가 보호한다.
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < n and 0 <= ny < m):
                continue

            if graph[nx][ny] == 1 and group[nx][ny] == -1:
                queue.append((nx, ny))
                group[nx][ny] = group_number


for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().rstrip().split())
    graph = [[0] * m for _ in range(n)]
    group = [[-1] * m for _ in range(n)]

    for _ in range(k):
        y, x = map(int, sys.stdin.readline().rstrip().split())
        graph[x][y] = 1

    group_number = 0

    for x in range(n):
        for y in range(m):
            # 배추가 심어져 있고, 배추흰지렁이가 없다면 추가한다.
            if graph[x][y] == 1 and group[x][y] == -1:
                group_number += 1
                bfs(x, y, group_number)

    # 필요한 배추흰지렁이 최소 마리 수
    print(group_number)