[프로그래머스/python] 무인도 여행

[풀이 방법]

• 그래프 탐색을 통해 무인도를 탐색해준다.
• 리스트 내의 값들이 string 형태이므로 list로 변환하여 사용하면 더 편하다.
• 탐색 함수 안에서 조건문을 통해 list의 Index를 벗어나지 않도록 설정해준다.
• 파이썬은 재귀함수의 깊이를 제한하므로 반복문을 통해 문제를 해결하거나, sys함수를 통해 깊이를 늘려줘야한다.

*이러한 문제 종류들을 만날 때, 항상 많이 헤메었었다. 리스트 내의 값을 확인 해야할 때는 '그래프 탐색'을 먼저 떠올릴 수 있으면 좋을 것 같다.

 

[풀이 코드]

import sys

sys.setrecursionlimit(1000000)


def search(maps, row, column, visited, value):
    if (row, column) in visited or 0 > row or row > len(maps) - 1 or column < 0 or column > len(maps[0]) - 1 or \
            maps[row][column] == 'X':
        return value
    value += int(maps[row][column])
    visited.append((row, column))
    value = search(maps, row - 1, column, visited, value)
    value = search(maps, row + 1, column, visited, value)
    value = search(maps, row, column - 1, visited, value)
    value = search(maps, row, column + 1, visited, value)

    return value


def solution(maps):
    answer = []
    visited = []
    maps = [list(Amap) for Amap in maps]
    value = 0

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'X' or (i, j) in visited:
                continue
            answer.append(search(maps, i, j, visited, value))

    return sorted(answer) if answer else [-1]