1012번: 유기농 배추 (python, 파이썬)

풀이(1)

import sys
sys.setrecursionlimit(10000)

t = int(sys.stdin.readline())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def bfs(vy, vx):
  for i in range(4):
    y = vy + dy[i]
    x = vx + dx[i]
    if M[y][x] == 1:
      M[y][x] = 0
      bfs(y,x)

for _ in range(t):
  m, n, k = map(int, sys.stdin.readline().split())
  M = [[0]*(m+2) for _ in range(n+2)]
  for i in range(k):
    x, y = map(int, sys.stdin.readline().split())
    M[y+1][x+1] = 1
  
  cnt = 0
  for i in range(1, n+1):
    for j in range(1, m+1):
      if M[i][j] == 1:
        M[i][j] = 0
        bfs(i,j)
        cnt += 1
  
  print(cnt)

배추밭(M)을 만들고, 이중 for문을 이용하여, 확인한 위치의 값을 0으로 바꾸는 bfs적용
시간: 76ms
코드길이: 599B

풀이(2)

import sys
sys.setrecursionlimit(10000)

t = int(sys.stdin.readline())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def bfs(L):
  for i in range(4):
    x = L[0] + dx[i]
    y = L[1] + dy[i]
    if ([x, y] in A):
      A.remove([x, y])
      bfs([x,y])

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

  cnt = 0
  while A:
    bfs(A.pop(0))
    cnt += 1

  print(cnt)

배추밭(M)을 만들지않고, 배추 위치의 배열(A)을 만들어 bfs적용
시간: 296ms
코드길이: 486B
* 리스트의 추가/삭제로 인해 시간이 오래걸림