문제 요약: maps라는 문자열 2차원 배열에서 'X'가 아닌 숫자들은 음식량을 의미하며, 상하좌우로 연결된 땅 덩어리(무인도)를 찾아 음식 총합을 구한 후 오름차순으로 정렬하는 문제.
🧪 [프로그래머스 무인도 여행] 첫 시도 - Python 재귀 DFS
처음엔 DFS로 연결된 지점을 탐색해 음식량을 누적하려고 했습니다. 이때 숫자 누적이 잘 안 돼서 temp_list라는 전역 리스트를 써서 처리했어요.
import sys
sys.setrecursionlimit(10 ** 6)
def solution(maps):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(_h, _w, path):
if (_h, _w) in visited or maps[_h][_w] == "X":
return path
visited.add((_h, _w))
temp_list.append(int(maps[_h][_w]))
for dh, dw in directions:
nh, nw = _h + dh, _w + dw
if 0 <= nh < len(maps) and 0 <= nw < len(maps[0]):
dfs(nh, nw, path + [(nh, nw)])
answer = []
visited = set()
for h in range(len(maps)):
for w in range(len(maps[0])):
if (h, w) in visited or maps[h][w] == "X":
continue
temp_list = []
dfs(h, w, [(h, w)])
answer.append(sum(temp_list))
return sorted(answer) if answer else [-1]
🐛 시행착오
RecursionError 발생 → Python은 재귀 깊이 제한이 기본 1000
정수 누적이 안 돼서 전역 리스트(temp_list)를 사용 → 비효율적
DFS 경로를 저장하려고 path + [(h, w)]로 리스트를 계속 복사 → 메모리 낭비
🔍 원인 분석
Python의 정수(int) 는 immutable → 함수 내부에서 += 해도 바깥에 반영 안 됨
리스트는 mutable이라 전역 리스트 방식은 동작하긴 하지만, 깔끔하지 않음
깊은 재귀 DFS는 sys.setrecursionlimit() 없이는 실전에서 불안정
✅ 무인도 여행 개선 풀이 - 리턴값 기반 Python DFS
전역 리스트 없이 dfs() 함수 자체가 음식량의 합을 반환하게 구성. 또한 visited는 2차원 배열로 관리해서 더 직관적입니다.
def solution(maps):
h_len = len(maps)
w_len = len(maps[0])
visited = [[False] * w_len for _ in range(h_len)]
answer = []
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(h, w):
visited[h][w] = True
total = int(maps[h][w])
for dh, dw in directions:
nh, nw = h + dh, w + dw
if 0 <= nh < h_len and 0 <= nw < w_len:
if not visited[nh][nw] and maps[nh][nw] != 'X':
total += dfs(nh, nw)
return total
for h in range(h_len):
for w in range(w_len):
if not visited[h][w] and maps[h][w] != 'X':
answer.append(dfs(h, w))
return sorted(answer) if answer else [-1]
🧠 total += dfs(...) 는 어떻게 동작할까?
dfs(...)는 무인도 하나의 음식량 총합을 리턴하는 함수입니다.
재귀 구조상, 하위 호출의 리턴값이 상위 함수로 전달되고, total += ... 형태로 누적됩니다.
"X"이거나 이미 방문한 노드는 애초에 재귀 호출하지 않기 때문에 누락되지 않고 정확히 한 번만 더해집니다.
🤔 코딩 테스트 DFS 풀이 회고 - 무인도 여행 문제에서 배운 점
재귀 DFS는 코드가 간결하지만, Python 환경에서는 깊이 제한을 반드시 고려해야 한다.
