BOJ - 1012

백준 문제 링크
유기농 배추

❓접근법

1. '단지번호붙이기' 문제와 유사해서 BFS 방식을 사용했다.
2. 좌표의 값이 1이라면 queue에 넣어주고, count를 1 더해준다.
   그래서 총 연결되어있는 1의 개수만큼 count를 구하고, 더이상 없을 경우 count를 return하는 함수를 만들었다.
3. 지도의 크기만큼 함수를 적용해야 하므로, for문 2개로 지도의 원소에 접근하여 값이 1이라면 좌표를 함수에 넣어서 count를 구해줬다.
4. 우리가 구해야 하는 것은 연결되어 있는 1의 개수가 아닌
   1이 모여있는 것의 개수를 구하는 것이므로,
   temp에 count를 넣어주고, 반복문 밖에서 answer에 len(temp)를 넣어줬다.
   즉, temp = [3,2,2,1,6] 이런 식으로 나타날 텐데 len(temp) = 5이므로 answer에 5를 넣어준다.

👌🏻코드

from collections import deque

T = int(input())
answer = []


for _ in range(T):
    M,N,K = map(int, input().split())
    
    lst = [[0] * (M) for _ in range(N)]
    
    
    for _ in range(K):
        a,b = map(int, input().split())

        lst[b][a] = 1


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

    def bfs(x,y):
        queue = deque()
        queue.append((x,y))

        lst[x][y] = 0

        count = 0

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

            count += 1

            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]

                if (0<=nx<N) and (0<=ny<M) and (lst[nx][ny] == 1):
                    lst[nx][ny] = 0
                    queue.append((nx,ny))

        return count

    temp = []
    for i in range(len(lst)):
        for j in range(len(lst[0])):
            if lst[i][j] == 1:
                count = bfs(i,j)
                temp.append(count)
    answer.append(len(temp))
    
for i in answer:
    print(i)

좀 헤맸던 부분은 문제의 조건에서
'그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.' 이 부분과 주어진 X,Y 좌표가 이해가 안되어서 좀 헤맸다.