백준 1012번 : 유기농 배추

class를 깨면 백준 티어가 빨리 오른다는 말을 듣고 class에 있는 문제들을 하나씩 풀어보던 중, 완탐 문제를 마주하게 되었다.

전체 코드

import sys
input = sys.stdin.readline
# 2차 수정
sys.setrecursionlimit(10000) 


def DFS(table, visited, i, j):
    visited[i][j] = True
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for a in range(4):
        ni = i + dx[a]
        nj = j + dy[a]
        # 1차 수정
        if (0 <= ni < n) and (0 <= nj < m):
            if (not visited[ni][nj]) and (table[ni][nj] == 1):
                DFS(table, visited, ni, nj)
    


case = int(input())
for _ in range(case):
    # input
    m, n, k = map(int, input().split())
    table = [[0] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        table[y][x] = 1
    
    # DFS 로 몇 묶음 있는 지 확인
    visited = [[False] * m for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if (not visited[i][j]) and (table[i][j] == 1):
                DFS(table, visited, i, j)
                count += 1

    print(count)

완전 탐색의 아주 기본적인 문제임에도 불구하고 부끄럽게도 3차 시도만에 맞추었다.

1차 시도

import sys
input = sys.stdin.readline


def DFS(table, visited, i, j):
    visited[i][j] = True
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for a in range(4):
        ni = i + dx[a]
        nj = j + dy[a]
        
        # 1차 시도에서 이 부분이 문제가 되었음.
        if (0 <= ni < n) and (0 <= nj < m) and (not visited[ni][nj]) and (table[ni][nj] == 1):
                DFS(table, visited, ni, nj)

1차 때 ni, nj의 범위를 고려하기 전에 visited[ni][nj]) and (table[ni][nj] == 1) 에 값이 들어가버려서 오류가 났다.

2차 시도

def DFS(table, visited, i, j):
    visited[i][j] = True
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for a in range(4):
        ni = i + dx[a]
        nj = j + dy[a]
        if (0 <= ni < n) and (0 <= nj < m):
            if (not visited[ni][nj]) and (table[ni][nj] == 1):
                DFS(table, visited, ni, nj)

그런데 다시 한 번 런타임에러를 마주하게 되었다... 이번엔 다행히 바로 알아내었다. 파이썬의 재귀 깊이 제한은 1000으로 매우 낮기 때문에 오류가 발생하는 것이었다.

이 기회에 재귀함수에 대해 더 알아보았다.

재귀는 간단히 말해서, 함수가 자기 자신의 함수를 호출하도록 구현하는 방식이다. 그래서 반복문과 마찬가지로 종료 조건을 반드시 생성해주어야 무한 반복에 빠지지 않는다.

• 재귀함수와 스택 메모리
  재귀함수는 함수가 종료되지 않고 계속해서 함수가 호출되기 때문에 스택 공간이 초과되는 스택 오버플로가 발생할 수 있다.

프로그램을 실행하기 위해서는 운영체제로부터 메모리 공간을 할당받아야 한다.

• 정적 할당 영역

1. 코드 영역 : 실행할 프로그램 코드가 저장됨
2. 데이터 영역 : 프로그램이 사용하려고 미리 정의한 변수와 데이터가 저장됨

• 동적 할당 영역

3. 스택 영역 : 프로세스 실행을 위한 함수의 호출과 관계되는 지역 변수 및 매개변수가 저장되는 영역
4. 힙 영역 : 프로그램이 실행되는 동안 사용자가 직접 메모리를 관리할 수 있는 메모리 영역

재귀함수가 호출되면 동적 할당 영역 중 스택 영역에 함수와 관련된 지역 변수와 매개변수 등이 임시로 저장되게 된다. 스택 영역은 함수가 호출될 때부터 종료될 때까지만 사용된다.

3차 시도

sys.setrecursionlimit(10000) 

재귀 깊이 제한을 늘려주어 해결!