백준 - 1012번 유기농 배추

탐색 - 1012번 유기농 배추

나의 코드)

import sys
sys.setrecursionlimit(10000)

#dfs 사용
def dfs(x,y):

  # 배추밭 크기 벗어났을시에 false
  if x < 0 or  y< 0 or x>=n or y>=m:
    return False
    
   #  심을 수 없는 자리엔 false 
  if graph[x][y] ==0:
    return False
    
    # 심을 수 있다면 
  if graph[x][y] == 1:
    
    # 방문 표시
    graph[x][y] = 0
    
    # 재귀로 불러낸 dfs들의 return 값은 생각안해도 된다.
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)
    
    return True
    
  return False



test_case = int(input())

#테스트 케이스
for _ in range(test_case):
	
  # 변수 받고 배추 밭 만들기  
  result = 0
  n,m,k = map(int,input().split())
  graph = [[0 for _ in range(m)] for _ in range(n)]

   # 배추 위치 받기	
  for i in range(k):
    ix, iy = map(int,input().split())
    graph[ix][iy] = 1

  for i in range(n):
    for j in range(m):
 
       # True 개수만큼 결과 더해주기
      if dfs(i,j) == True:
        result +=1
  print(result)

comment)
생각보다 쉽게 풀었다. 일단 내가 이코테에서 풀었던 음료수 얼려먹기와 비슷한 문제여서 문제분류는 bfs로 되어있지만 dfs를 이용해서 풀었다. 처음엔 시간초과 뜰까봐 알고리즘은 맞는지 볼려고 python 대신 pypy로 제출했는데 맞아서 좋았다. 하지만 바로 파이썬 돌리자마자 런타임 떠서 당황 ;; 보니까 파이썬의 재귀 깊이는 1000인데 그걸 넘어가서 재귀오류가 뜬 것이였다.
그래서 이번에 배운건 sys모듈이다. 아 그리고 sys.readline도 다시공부해야겠다고 느꼈다 .

import sys
sys.setrecursionlimit(10000)
# 재귀 깊이가 10000으로 설정됨.

ㅋㅋㅋㅋㅋ 풀어지긴 하는 구나 개꿀딱