1012번: 유기농 배추

Problem Link
https://www.acmicpc.net/problem/1012

✅ Problem Summary

주어진 행렬에서 수평(horizontally), 수직(vertically)으로 이어진 구역의 갯수를 세는 문제

---

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search)

그림출처:Wikipedia

---

📑 My Answer

• 메모리 : 33220KB
• 시간 : 396ms

import sys
sys.setrecursionlimit(10**6)

def dfs(matrix, matsize, pos):
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    matrix[pos[0]][pos[1]] = 0
    for i in range(4):
        ni, nj = pos[0]+dy[i], pos[1]+dx[i]
        if 0<=ni<matsize[0] and 0<=nj<matsize[1] and matrix[ni][nj] == 1:
            matrix = dfs(matrix, matsize=matsize, pos=(ni, nj))
    return matrix
    
def main():
    T = int(input())
    result = []
    for _ in range(T):
        M, N, K = map(int, input().split())
        matrix, cnt = [[0]*M for _ in range(N)], 0
        for _ in range(K):
            X, Y = map(int, input().split())
            matrix[Y][X] = 1
        for i in range(N):
            for j in range(M):
                if matrix[i][j] == 1:
                    matrix = dfs(matrix, matsize=(N, M), pos=(i, j))
                    cnt += 1
        result.append(cnt)
    print(*result, sep='\n')
        
main()

---