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

DFS 유형의 다른 문제 도전!!

 

배추밭 안에 배추의 좌표값이 주어지고 해당 좌표와 상하좌우로 연결된 좌표에도 배추가 있으면 하나의 구역으로 취급한다. 한 구역마다 배추흰지렁이 1마리가 사는데 배추밭에 있는 총 지렁이의 마리 수를 출력하자.

 

1012번 유기농 배추 풀이

[시도1] 맞았습니다!! with 솔루션

T = int(input()) #케이스 개수

#케이스 개수 만큼 코드 작동
while T > 0:
  N, M, K = map(int, input().split()) #각각 세로, 가로, 좌표 개수
  field = [[0]*N for i in range(M)] #배추밭
  
  #배추밭 배추 좌표 입력받기
  for _ in range(K):
    x, y = map(int, input().split())
    field[y][x] = 1 
  
  def dfs(i,j):
  	#배추밭 범위 안에서 확인하기
    if i <= -1 or i >= M or j <= -1 or j >= N:
      return False
    
    #배추(1)가 있으면 확인했다는 의미로 0으로 바꾸기
    if field[i][j] == 1:
      field[i][j] = 0
      #상하좌우 연결된 배추 확인
      dfs(i-1,j)
      dfs(i,j-1)
      dfs(i+1,j)
      dfs(i,j+1)
      return True #연결된 배추 구역 확인 후 True 반환
    return False
  
  result = 0
  for i in range(M):
    for j in range(N):
      #해당 위치가 배추로 이어져 있음이 확인되면 벌레 1마리 추가
      if dfs(i, j) == True:
        result += 1
  
  print(result) #결과출력
  T -= 1 #케이스 하나 완료

이전에 풀었던 "이것이 취업을 위한 코딩 테스트다" 책에 있는 DFS 문제인 음료수 얼려 먹기 문제랑 유사했다.

하지만 문제를 보자마자 아 이 문제는 어떻게 풀어야 한다는 것을 바로 알지는 못하는 것 같다.. 그렇게 될 수 있도록 공부 열심히 해야 할 것 같다.

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

1012번: 유기농 배추