[백준/BFS&BFS] 1012번: 유기농 배추 (실버2, python)

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

1012번: 유기농 배추

아이디어

bfs로 풀었다.

배추가 있는 곳의 위치를 미리 알려줘서 좋았다 ㅎㅎㅎ (2중 포문을 안써도 되니까!)

주의할 점은 문제의 (x, y)는 (가로, 세로)이기 때문에 이중리스트에서 해당 위치를 찾을 때는 [y][x]로 찾아야 한다.

전체 코드

from collections import deque

dv = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def bfs(x, y, visited):
    queue = deque([(x, y)])
    visited[x][y] = 1

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

        for dx, dy in dv:
            nx = x + dx
            ny = y + dy
        
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and maps[nx][ny] == 1:
                visited[nx][ny] = 1
                queue.append((nx, ny))

            
T = int(input())
for _ in range(T):

    M, N, K = map(int, input().split())

    pos = []
    for i in range(K):
        pos.append([int(x) for x in input().split()])
   
    maps = [[0] * M for _ in range(N)]
    for x, y in pos:
        maps[y][x] = 1

    visited = [[0] * M for _ in range(N)]
    count = 0
    for x, y in pos:
        if visited[y][x] == 0:
            bfs(y, x, visited)
            count += 1

    print(count)