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

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

 

 

 

Python

import sys
from collections import deque
dx = [0,0,-1,1]
dy = [1,-1,0,0]

t = int(sys.stdin.readline())
for i in range(t):
    m, n, k = map(int, sys.stdin.readline().split())
    visit = [[0 for i in range(m)] for i in range(n)]
    cabage = [[0 for i in range(m)] for i in range(n)]
    
    for i in range(k):
        x, y = map(int, sys.stdin.readline().split())
        cabage[y][x] = 1

    q = deque()
    cnt = 0
    
    for a in range(n):
        for b in range(m):
            if cabage[a][b] == 0 or visit[a][b] > 0:
                continue
            visit[a][b] = 1
            q.append((a,b))

            while len(q) != 0:
                pos = q.popleft()
                for i in range(4):
                    nx = pos[1] + dx[i]
                    ny = pos[0] + dy[i]
                    if 0<=nx<m and 0<=ny<n:
                        #print((ny,nx),end=" ")
                        if visit[ny][nx] == 0 and cabage[ny][nx]==1:
                            visit[ny][nx] = visit[pos[0]][pos[1]] + 1
                            q.append((ny,nx))
                    #print()
            cnt+=1
            #print(cnt, (b,a))
            #for i in range(n):
            #    print(visit[i], cabage[i])
            
    print(cnt)

 

 

 

입력되는 좌표가 배열의 특성과 반대로 입력되는 것에 주의하여 인덱스 접근