[백준] 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]가 된다.
- 가로*세로가 범위 안ㄴ에 배추가 있다면 큐에 추가하고 0으로 변경해준다.
Author And Source
이 문제에 관하여([백준] 1012번 : 유기농 배추 (파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yj_lee/백준-1012번-유기농-배추-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)