BOJ 2468 안전 영역
BFS가 아직 손에 익지 않아서 대부분의 문제를 DFS로 풀고 있습니다.
이 문제의 경우 메모리 초과가 일어나서 BFS로 풀이를 한 경우가 많습니다.
저의 경우 DFS로 풀이하였습니다.
정답 코드
import sys
sys.setrecursionlimit(15000)
def dfs(x, y, height):
visited[x][y] = True
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < n and 0 <= ny < n:
if not visited[nx][ny] and graph[nx][ny] > height:
dfs(nx, ny, height)
n = int(input())
graph = [list(map(int ,input().split())) for _ in range(n)]
max_height = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
for j in range(n):
if graph[i][j] > max_height:
max_height = graph[i][j]
max_safe_area = 0
for height in range(max_height + 1):
visited = [[False] * (n) for _ in range(n)]
safe_area = 0
for i in range(n):
for j in range(n):
if not visited[i][j] and graph[i][j] > height:
dfs(i, j, height)
safe_area += 1
max_safe_area = max(max_safe_area, safe_area)
print(max_safe_area)풀이과정
현재 이 코드의 경우 max_height를 저렇게 지정하여 현재 그래프에서 가장 큰 값을 max_height로 잡습니다.
이 방법 외에도 검색을 해보았더니 for문의 범위를 1부터 100까지 지정해주어서 모든 경우를 전부 구하는 방법도 있습니다.
브루트포스적으로 해결한 것 같지만 저는 최대로 나올 수 있는 높이를 찾기 위해 저렇게 코드를 작성하였습니다.
이렇게 풀이하는게 성능적으로 좋을 것이라고 생각했습니다.
또한 visited 리스트 또한 한번만 돌리는 것이 아니라 높이가 달라졌을 때
새롭게 다시 방문을 체크해야하기 때문에 for문안에 넣어서 초기화 되도록 설정하였습니다.
메모리 초과가 나는 이유?
저도 이유를 모르겠어서 서칭을 해보아서 15000으로 지정하는 방법을 찾았습니다.
제가 생각하는 이유는 데이터 구조가 너무 커졌기 때문이라고 생각합니다.
이 문제의 경우 N의 최댓값은 100으로 N * N을 하면 100000 Size의 그래프가 형성이 되고 이를 재귀를 시행하는데 그 재귀도 한번이 아니라 굉장히 여러번 일어나게 됩니다.
max_height를 지정하고 0부터 max_height까지의 연산을 계속해서 재귀로 수행하기 때문에 많은 범위가 일어나서 메모리가 터지게 됩니다.
ChatGPT의 답변
재귀 깊이 제한: sys.setrecursionlimit() 함수는 재귀 함수의 최대 깊이를 설정하는 함수입니다. 즉, 재귀 함수를 몇 번까지 호출할 수 있는지를 제한하는 역할을 합니다. sys.setrecursionlimit(100000)은 재귀 함수 호출 깊이 제한을 100000으로 설정한다는 의미이고, sys.setrecursionlimit(15000)은 재귀 함수 호출 깊이 제한을 15000으로 설정한다는 의미입니다. 이 값은 재귀 함수가 얼마나 깊게 호출될 수 있는지를 결정합니다.
메모리 사용량: 재귀 호출을 사용하는 경우, 스택에 호출된 함수의 정보가 쌓이게 됩니다. 따라서 재귀 호출 깊이가 깊을수록 메모리 사용량도 늘어납니다. sys.setrecursionlimit(100000)은 재귀 호출 깊이 제한을 크게 늘리므로, 재귀 호출을 많이 사용하는 코드에서는 더 많은 메모리를 사용하게 될 수 있습니다. 반면에 sys.setrecursionlimit(15000)은 제한을 낮추므로 메모리 사용량이 적어질 가능성이 있습니다.
따라서 재귀 호출을 사용하는 코드에서는 재귀 깊이 제한을 어떻게 설정하느냐에 따라 메모리 사용량이나 코드 실행에 영향을 미칠 수 있습니다. 그러나 이 값의 설정 자체보다는 코드를 어떻게 구성하느냐에 따라 효율적인 메모리 사용과 실행이 가능합니다.
문제를 풀이하고
처음 문제를 보고 단지번호 붙이기와 유사하다고 생각되어 풀이를 시작했습니다.
다만 고려해야할 점들이 상당히 많았고 처음에 문제가 이해가 잘 되지 않았습니다.
진짜 처음에 제가 생각해도 멍청한 사람인가라고 느꼈던게
'어.. 이거 높이가 0이면 안 잠기니까 제일 많은거 아닌가? 라는 생각까지 했습니다'
이 경우 답은 1이 나오는데 문제 이해를 또 시작부터 잘못해서 고생할뻔 했습니다.
모두 문제 이해를 제대로 하고 코드를 작성하기 시작하는 습관을 들입시다,,
이 습관이 들지 않고 시작부터 일단 코드를 작성하는 버릇이 들어서 설계를 우선적으로 하는 습관을 들이고 있는데 쉽지 않은 것 같습니다.
