[백준 1012] 유기농 배추 (Python)

👩🏻‍💻문제링크

[백준 1012] 유기농 배추 (Python)

✍️Idea Sketch

2021-08-02

1. 단지번호붙이기와 같은 DFS 로직

2. 오랜만에 풀어서 잊은 것

• main에서 dfs()를 호출할 때
• 이중반복문을 사용해서
• 2차원 배열 graph 의 모든 원소를 확인한다

3. dx dy 사용 시 소요시간 4ms 증가 (96ms)

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

def dfs(x, y):
  if (0<=x<n) and (0<=y<m):
    if graph[x][y] == 1:
      graph[x][y] = -1
      for i in range(4):
        dfs(x+dx[i], y+dy[i])
      return True
  return False

✍️소스코드

2021-08-02 92ms 통과

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y):
  if (0<=x<n) and (0<=y<m):
    if graph[x][y] == 1:
      graph[x][y] = -1
      dfs(x-1, y)
      dfs(x+1, y)
      dfs(x, y+1)
      dfs(x, y-1)
      return True
  return False

if __name__ == "__main__":
  t = int(input())
  for _ in range(t):
    n, m, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]

    for _ in range(k):
      x, y = map(int, sys.stdin.readline().rstrip().split())
      graph[x][y] = 1

    cnt = 0
    for i in range(n):
      for j in range(m):
        if dfs(i, j) == True:
          cnt += 1

    print(cnt)