[백준] 1012. 유기농 배추 / python 파이썬

🚩 그래프이론, 그래프탐색, DFS, BFS

 

thinking

상하좌우 다 탐색하면서 방문탐색하고 값이 1이면(==배추면) 카운팅 1 증가

⭐ 처음에 그냥 풀었더니 런타임에러가 났다.

구글링 했더니 재귀 limit을 설정해주지 않아서 발생한 문제라고 한다.

K(1 ≤ K ≤ 2500)의 범위가 엄청 커서 그런듯?

파이썬의 기본 재귀 한도가 (1000)이어서 재귀 깊이가 1000을 넘어갈 경우 모듈을 추가해줘야한다.

---

파이썬 최대 재귀 깊이 늘리는 모듈

import sys 
sys.setrecursionlimit(탐색하고자하는 깊이)

 

 

코드

import sys
sys.setrecursionlimit(10000)

def dfs(r,c):
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    a[r][c] = -1  # 방문체크
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if nr < 0 or nr >= N or nc < 0 or nc >= M:  # 범위체크
            continue
        if a[nr][nc] == 1:
            a[nr][nc] = -1  # 방문체크
            dfs(nr,nc)

T = int(input())
for tc in range(1, T+1):
    M, N, K = map(int, input().split())  # M:가로길이(열 길이), N:세로길이(행 길이), K:배추개수
    a = [[0] * M for _ in range(N)]  # 배추밭

    for _ in range(K):  # 배추 1로 바꾸기
        c, r = map(int, input().split())
        a[r][c] = 1

    cnt = 0
    for i in range(N):
        for j in range(M):
            if a[i][j] == 1:  # 배추면 카운트+1 & 방향 탐색
                dfs(i,j)
                cnt += 1

    print(cnt)

 

 

한줄후기

백준은 런타임에러가 뜨면 뭐때문에 뜬 건지 알려줬음 좋겠다