BaekJoon - 1012번: 유기농 배추 (그래프, 탐색)

2023. 2. 15. 04:40·Coding Test/BaekJoon_Python
728x90

DFS 문제를 통해 여러 시행착오를 거칠 필요가 있다고 생각했던 나는 한 문제를 더 찾아서 풀기 시작했고,

재귀 함수를 이용했기에 발생했던 런타임 에러가 발생했다

해결법도 찾았고, 그 방법까지 해서 이번 글에 포스팅하려고 한다


문제

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

 


문제 분석

이 문제는 DFS를 이용하여 블록단위 탐색을 이용하면 되지만 몇 가지 유의사항이 존재한다

  1. 그래프 형태로 존재하는 것이 아닌 좌표단위로 존재하는 것 -> 가상의 그래프 맵을 만든다
  2. 배추밭이 굉장히 넓어졌을 때 재귀를 이용할 경우 깊이의 한계에 막히는 것 -> sys를 import해서 이를 방지한다

코드 작성

# Python 자체의 최대 재귀 깊이가 달라질 수 있기에 1000회가 넘을 것으로 예상되면
# sys.setrecursionlimit(10**6)으로 10억회를 설정해서 recursion error을 피하도록 하자
import sys
sys.setrecursionlimit(10**6)

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

# 재귀를 이용한 상하좌우 DFS 블록탐색 함수


def dfs(xpos, ypos):
    if xpos >= N or xpos <= -1 or ypos >= M or ypos <= -1:
        return False

    if d[xpos][ypos] == 1:
        d[xpos][ypos] = 0
        dfs(xpos + 1, ypos)
        dfs(xpos - 1, ypos)
        dfs(xpos, ypos + 1)
        dfs(xpos, ypos - 1)
        return True

    return False


# 테스트 케이스 만큼 반복
for _ in range(T):
    M, N, K = map(int, input().split())
    d = [[0] * M for _ in range(N)]
    for i in range(K):
        # 여기서 주의할 점: y, x의 형태로 심어지므로 좌표값을 변경할 때 주의하자
        x, y = map(int, input().split())
        d[y][x] = 1
    result = 0
    # 2중 반복문으로 블록 개수 탐색
    for i in range(N):
        for j in range(M):
            if dfs(i, j) == True:
                result += 1
    print(result)

RuntimeError : recursion Error 이 발생하는 이유는 Python 자체에서 재귀함수의 재귀 깊이를 막아놓았기 때문인데,

Python에서는 10억회를 무한에 가까운 수로 지정하고 있기에

sys를 불러와서 setrecursionlimit을 10억회로 지정해둔다면 이 에러가 해결된다


실행 및 마무리

Test case 1 : 5 / Test case 2 : 1

정상적으로 출력 되는 모습을 볼 수 있다!


End

728x90
저작자표시 비영리 변경금지 (새창열림)

'Coding Test > BaekJoon_Python' 카테고리의 다른 글

BaekJoon - 2667번: 단지번호붙이기 (그래프, 탐색)  (0) 2023.02.15
BaekJoon - 6550번: 부분 문자열 (문자열, 그리디 알고리즘)  (0) 2023.02.12
BaekJoon - 14584번: 암호 해독 (문자열, 브루트포스 알고리즘)  (0) 2023.02.11
BaekJoon - 5597번: 과제 안 내신 분..? (1차원 배열, PYTHON)  (1) 2022.11.01
BaekJoon - 10807번: 개수 세기 (1차원 배열, PYTHON)  (0) 2022.11.01
'Coding Test/BaekJoon_Python' 카테고리의 다른 글
  • BaekJoon - 2667번: 단지번호붙이기 (그래프, 탐색)
  • BaekJoon - 6550번: 부분 문자열 (문자열, 그리디 알고리즘)
  • BaekJoon - 14584번: 암호 해독 (문자열, 브루트포스 알고리즘)
  • BaekJoon - 5597번: 과제 안 내신 분..? (1차원 배열, PYTHON)
ThreeLight
ThreeLight
ThreeLight Studio의 블로그, TimeMap.exe에 오신 것을 환영합니다.
  • ThreeLight
    TimeMap.exe
    ThreeLight
  • 전체
    오늘
    어제
    • 분류 전체보기 (245)
      • Checkpoint (1)
      • (3D)Dev Deep Dive (0)
        • Templates & Guides (9)
        • Frontend origin (9)
        • Backend origin (1)
        • TroubleShootings (4)
      • Development Study (95)
        • Frontend (36)
        • Backend (21)
        • CS(Computer Science) (2)
        • Background Knowledges (11)
        • Algorithm (2)
        • Mobile (3)
        • AWS (6)
        • Python (6)
        • MSW(MapleStoryWorlds) (8)
      • Coding Test (59)
        • 문제.zip (1)
        • BaekJoon_JavaScript (0)
        • Programmers_JavaScript (9)
        • BaekJoon_Python (23)
        • Programmers_Python (10)
        • Undefined_Python (3)
        • Programmers_SQL (13)
      • 활동내역.zip (43)
        • 개인 (21)
        • Techeer (12)
        • Bootcamp (7)
        • Hackathon (1)
        • TeamProjects (2)
      • 여기 괜찮네??(사이트 | App) (5)
      • 재미있는 주제들 (8)
      • 개발 외 공부 저장소 (11)
        • 생산운영관리 (3)
        • 생활속의금융 (6)
        • 경영정보시스템 (2)
  • 링크

    • TimeMap.dmg (Portfolio)
    • GitHub 바로가기
    • 오픈프로필(카카오톡)
    • Medium 바로가기
    • Disquiet 바로가기
    • LinkedIn 바로가기
  • 인기 글

  • 태그

    TypeScript
    HTML
    CSS
    programmers
    프로그래머스
    SQL
    Baek Joon
    Python
    react
    JavaScript
  • 최근 글

  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.1
ThreeLight
BaekJoon - 1012번: 유기농 배추 (그래프, 탐색)
상단으로

티스토리툴바