[프로그래머스] 무인도 여행 - Python

코딩테스트 연습 - 무인도 여행 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 요약

지도 격자의 각 칸에는 'X' (바다)또는 1에서 9 사이의 자연수(무인도)가 적혀있습니다.

이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다.

지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다.

각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

 

매개변수 : 지도를 나타내는 문자열 배열 maps

return 값 : 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담고,  만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return

 

문제 풀이

dfs(깊이 우선 탐색)을 사용해서 풀어주면 된다.

무인도에 방문한 뒤 'X'로 표시를 해주어 다시 방문하지 않도록 처리했다.

import sys
sys.setrecursionlimit(10**7)

def dfs(answer, graph, x, y):
    n,m = len(graph), len(graph[0])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0<= ny < m:
            if graph[nx][ny] != 'X':
                answer[-1] += int(graph[nx][ny])
                graph[nx][ny] = 'X'
                dfs(answer, graph, nx, ny)
        
def solution(maps):
    answer = []
    n,m = len(maps), len(maps[0])
    graph = []
    for i in range(n):
        graph.append(list(maps[i]))
        
    for x in range(n):
        for y in range(m):
            if graph[x][y] != 'X':
                answer.append(int(graph[x][y]))
                graph[x][y] = 'X'
                dfs(answer, graph, x, y)

    answer.sort()
    if len(answer) == 0: return [-1]
    return answer

 

dfs로 풀 경우는 setrecursionlimit을 이용해서 재귀 깊이 한도를 늘려주어야 해결이 된다.