[프로그래머스 - lv2] 무인도 여행 / 파이썬

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

---

문제 풀이)

DFS를 이용해 문제를 풀었다.

해당 map에서 방문하지 않고 갈수있는 섬이면 방문 처리를 한후 스택에 할당 이후 재귀적으로 주변 섬들을 탐색해 만약 연결되어 있다면 식량들을 전부 합해 return해주도록 DFS 함수를 구현했다.

 def dfs(i, j, visited):
        if 0<= i < n and 0 <= j < m: # 주어진 map의 범위 안에 있고
            if not visited[i][j] and maps[i][j] != 'X': # 방문하지 않았고 갈수 있는 곳이면
                visited[i][j] = True
                L = dfs(i, j-1, visited) # 왼쪽 섬
                R = dfs(i, j+1, visited) # 오른쪽 섬
                U = dfs(i+1, j, visited) # 위쪽 섬
                D = dfs(i-1, j, visited) # 아래쪽 섬
                return int(maps[i][j]) + L + R + U + D
            else:
                return 0
        else:
            return 0

전체 코드는 다음과 같다.

 

단 DFS 수행시 재귀호출스택 에러가 나지 않게 sys.setrecursionlimit을 넉넉하게 정해주었다.

 

import sys
sys.setrecursionlimit(int(1e7)) # 재귀호출 스택에러 발생 방지
def solution(maps):
    answer = []
    n = len(maps)  # row
    m = len(maps[0])  # col
    visited = [[False] * m for _ in range(n)]
	
    # DFS
    def dfs(i, j, visited):
        if 0<= i < n and 0 <= j < m:
            if not visited[i][j] and maps[i][j] != 'X':
                visited[i][j] = True
                L = dfs(i, j-1, visited)
                R = dfs(i, j+1, visited)
                U = dfs(i+1, j, visited)
                D = dfs(i-1, j, visited)
                return int(maps[i][j]) + L + R + U + D
            else:
                return 0
        else:
            return 0

    for i in range(n):
        for j in range(m):
            if not visited[i][j] and maps[i][j] != 'X': # 방문하지 않고 갈수있는 곳이면
                tmp = dfs(i, j, visited) # DFS 수행
                if tmp > 0:
                    answer.append(tmp)
    if answer:
        answer.sort()
        return answer
    else:
        return [-1]