프로그래머스 무인도 여행

 

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

간단한 dfs, bfs 문제이며 나는 dfs로 풀었다.

주어지는 탐색공간의 크기가 작아서 recursionlimit에 안 걸릴 줄 알았건만 recursion limit 때문에 오류가 발생한 지도 모르고 잠깐 고생했었다. 문제를 dfs로 푼다면 recursionlimit을 설정해 주는 것을 까먹지 말자

import sys
sys.setrecursionlimit(1000000)

idx = [[0,1],[1,0],[-1,0],[0,-1]]

def dfs(x, y, visited, matrix, food):
    
    visited[x][y] = True
    food = food + int(matrix[x][y])
    
    for each in idx:
        
        new_x = x + each[0]
        new_y = y + each[1]
        
        if 0 <= new_x < len(matrix) \
            and 0 <= new_y < len(matrix[0]) \
            and not visited[new_x][new_y] \
            and matrix[new_x][new_y] != 'X':

            food = dfs(new_x,new_y, visited, matrix, food)
    
    return food
            

def solution(maps):
    
    matrix = maps
    visited = [[False]*len(matrix[0]) for _ in range(len(matrix))]
    
    result = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] != 'X' and not visited[i][j]:
                tmp = dfs(i,j,visited, matrix,0)
                result.append(tmp)

    if not len(result):
        return [-1]
    else:
        return sorted(result)