1012 유기농 배추 _python

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

1012번: 유기농 배추

지렁이 한마리가 2500개의 배추를 지킨다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

인접한 배추를 묶어서 하나로 본다. dfs, bfs 모두 사용가능한 문제인데 dfs로 풀었다. 

배추를 발견하면 상하좌우를 모두 탐색하며 배추를 발견하면 근처 배추를 찾고, 모두 지워버렸다.

다 지우고나면 ans를 1추가하는 방식으로 구현했다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""

"""

T = int(input())
dx = [1,-1,0,0]
dy = [0,0,1,-1]

for i in range(T):
    M,N,K = map(int,input().split())
    arr = [[False]*M for _ in range(N)]
    ans = 0
    for j in range(K):
        X,Y = map(int,input().split())
        arr[Y][X] = True

    # for aaa in range(N):
    #     print(*arr[aaa])

    for x in range(N):
        for y in range(M):
            if arr[x][y]:
                arr[x][y]=False
                stack = [(x,y)]
                while stack:
                    a,b = stack.pop()
                    for i in range(4):
                        xi = a+dx[i]
                        yi = b+dy[i]
                        if 0<=xi<N and 0<=yi<M and arr[xi][yi]:
                            stack.append((xi,yi))
                            arr[xi][yi] = False
                ans+=1
    # for aaa in range(N):
    #     print(*arr[aaa])            
    print(ans)