[백준] 1012번 : 유기농 배추 (파이썬)

문제

나의 답안

from collections import deque #bfs 풀

t=int(input())

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

def bfs(x,y):
    que=deque()
    que.append((x,y))
    arr[x][y]=0

    while que:
        xx,yy=que.popleft()#배추가 있는 곳 좌표
        for i in range(4):#상하좌우 탐색
            nx=xx+dx[i]
            ny=yy+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and arr[nx][ny]==1:
                #범위를 만족하고 배추가 있다면
                que.append((nx,ny))#덱큐에 추가하고
                arr[nx][ny]=0#0으로 변경
            
        

for i in range(t):
    m,n,k=map(int,input().split())#가로 세로 개수
    arr=[[0]*m for ii in range(n)]#밭 생성
    cnt=0#벌레 개수==구역의 수
    
    for j in range(k):
        x,y=map(int,input().split())#좌표
        arr[y][x]=1#배추가 있는 곳 표시, 행과 열 주의

    for a in range(n):#배추가 있는지 없는지 검사
        for b in range(m):
            if arr[a][b]==1:#있다면
                bfs(a,b)#탐색
                cnt+=1#개수 증가
    print(cnt)

접근 방법

• bfs로 풀고자 deque를 사용하였다.
• 배추가 있는 곳은 1로, 없는 곳은 0으로 표기하고 탐색 후 1을 0으로 변경해준다.
• bfs이므로 y값을 기준으로 가로로 탐색하기 때문에 배추가 있는 곳은 arr[y][x]가 된다.
• 가로*세로가 $m \times n$ 범위 안ㄴ에 배추가 있다면 큐에 추가하고 0으로 변경해준다.