[백준] 1012 유기농 배추 - 파이썬

 

1012번: 유기농 배추

🥬문제 이해하기🥬

 

T는 밭의 개수, M,N,K는 밭의 가로길이, 세로길이, 심는 배추의 개수.

K개의 배추의 좌표는 그림을 그려보고 이해. 

애벌레는 상하좌우로만 움직여 인접해 있더라도 대각선에 있는 배추에는 이동하지 못함. 

 

🥬코드 구현🥬

import sys 
sys.setrecursionlimit(10000) 



#애벌레 개수세기
def dfs(x,y):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]

    #상하좌우 확인
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]

        #밭을 벗어나면 안됨
        if (0<=nx<M) and (0<=ny<N):
            if matrix[ny][nx]==1:
                matrix[ny][nx]=-1
                dfs(nx,ny)

test_case=int(input())


for _ in range(test_case):
    M,N,K=map(int,input().split())
    matrix=[[0]*M for i in range(N)]

    cnt=0
    #배추심기
    for i in range(K):
        a,b=map(int,input().split())
        matrix[b][a]=1

    #애벌레 개수 출력
    for i in range(N):
        for j  in range(M):
            if matrix[i][j]>0:
                dfs(j,i)
                cnt+=1

    print(cnt)

 

가로세로가 헷갈려서 몇 번 틀렸었다. 실제 matrix에서 사용하는 좌표와 배추를 심는 좌표가 반대이기 때문.