[백준/Python] 1012번 유기농 배추

---

문제

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

---

문제 풀이(정답)

from collections import deque

T = int(input())

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

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

def bfs(x, y):

    queue = deque([(x,y)])

    matrix[x][y] = 0

    while queue:

        x, y = queue.popleft()      # 방문 좌표 제거

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if nx < 0 or nx >= m or ny < 0 or ny >= n:

                continue

            if matrix[nx][ny] == 1:

                queue.append((nx, ny))

                matrix[nx][ny] = 0

for _ in range(T):

    m, n, k = map(int, input().split())

    matrix = [[0] * n for _ in range(m)] # 빈 배추밭

    cnt = 0

    for _ in range(k):

        x, y = map(int, input().split())

        matrix[x][y] = 1 # 배추 위치 표시

    for xx in range(m):

        for yy in range(n):

            if matrix[xx][yy] == 1:

                bfs(xx, yy)

                cnt += 1

    print(cnt)

 

dx,dy를 이용해서 상하좌우 방향 벡터를 정의한 후, BFS를 이용해 문제를 풀어주었다.

 

배추밭을 0과 1로 표현하고 방문한 곳은 0으로 처리해 그래프탐색문제로 풀어주었다.

나에게는 아직 어려운 문제..