[백준|파이썬] 1012: 유기농 배추 (실버2)

문제

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

1012번: 유기농 배추

 

 

🐍파이썬

실패한 코드

import sys
from collections import deque

t = int(sys.stdin.readline())
for i in range(t):
  m, n, k = map(int, sys.stdin.readline().split())
  baechu = [[0 for _ in range(m)] for _ in range(n)]
 
  for _ in range(k):
    a, b = map(int, sys.stdin.readline().split())
    baechu[b][a] = 1
    
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]

  def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    baechu[x][y] = 0
    while queue:
      x, y = queue.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= m or ny >= n or nx < 0 or ny < 0:
          continue
        if baechu[nx][ny] == 1:
          queue.append((nx, ny))
          baechu[nx][ny] = 0
    return

  cnt = 0
  for i in range(n):
    for j in range(m):
      if baechu[i][j] == 1:
        bfs(i, j)
        cnt += 1
  print(cnt)

BFS

import sys
from collections import deque

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    baechu[x][y] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= m or ny >= n or nx < 0 or ny < 0:
                continue
            if baechu[nx][ny] == 1:
                baechu[nx][ny] = 0
                queue.append((nx, ny))

t = int(sys.stdin.readline())
for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().split())	#m=가로, n=세로, k=배추갯수
    baechu = [[0 for _ in range(n)] for _ in range(m)]
    
    for _ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        baechu[a][b] = 1
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    cnt = 0
    for i in range(m):
        for j in range(n):
            if baechu[i][j] == 1:
                bfs(i, j)	
                cnt += 1	
    print(cnt)

1️⃣ 1로 연결된 지역을 하나의 구역으로 생각한다. 한 구역당 한 마리의 벌레가 필요하다.

2️⃣ 배추밭을 이동하며 값이 1인 지역을 발견하면 해당 지역을 0으로 덮어씌우고 그 지역의 상하좌우의 지역에 1이 있다면 마찬가지로 0으로 덮어씌운다. 연결된 지역을 더 이상 발견할 수 없다면 구역갯수를 체크하고 값이 1인 다른 구역을 찾는다. 이때, 이미 발견되었던 구역은 이미 0으로 덮어씌워졌기 때문에 다음번에 중복체크될 염려가 없다.

3️⃣ 모든 지역에 대한 탐색을 마쳤다면, 체크된 구역의 갯수를 프린트한다.