백준 1012번 : 유기농 배추

<문제>

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

1012번: 유기농 배추

---

<코드>

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(x, y):
    _x = [0, 0, 1, -1]
    _y = [1, -1, 0, 0]
    for i in range(4):
        m_x = x+_x[i]
        m_y = y+_y[i]
        if (0<=m_x and m_x <M) and (0<=m_y and m_y<N) and mat[m_x][m_y] ==1:
            mat[m_x][m_y] =0
            dfs(m_x, m_y)
num_list = []
T = int(input())
for _i in range(T):
    M, N, K = map(int, input().split())
    mat = [[0]*N for _j in range(M)]
    num = 0
    for _i in range(K):
        x, y = map(int, input().split())
        mat[x][y] = 1
    for i in range(M):
        for j in range(N):
            if mat[i][j] == 1:
                dfs(i, j)
                num +=1
    num_list.append(num)
for _i in range(T):
    print(num_list[_i])

 

---

<풀이>

배추밭을 Matrix형식으로 2x2 행렬로 배추가 심어진 곳을 1, 심어지지 않은 곳을 0으로 지정한다.

• [0,0]부터 탐색하여 특정 위치에서 값이 1인 경우 배추가 심어져 있음을 파악하고 이웃한 네 지점에 배추가 심어져 있는지 확인한다.
• 해당 조건으로 좌표값이 범위 내에 있고 이웃한 위치에서 원소값이 1인 경우 하나로 묶이므로 원소값을 0으로 변경해 준다 => 한 마리의 지렁이로 해당 영역을 커버할 수 있다.
• 모든 행렬의 각 위치에서 배추가 심어져 있는지 판단해야하므로 M*N개의 값에 접근한다.

---

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/1012

GitHub - Junuux/Algorithm