무인도 여행

 

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

프로그래머스

문제풀이

해당 문제는 dfs로 풀이하는 것이 효율적인 방법이다.

 

• 문자열은 불변한 데이터 이기 때문에 각 문자열을 리스트로 변환하여 그래프를 생성해 준다.
• 그래프의 현재 위치가 "X"가 아닐 경우 dfs를 호출해서 재귀적으로 각 위치의 정수를 더해주도록 하며 결과를 오름차 정렬한다.

import sys

sys.setrecursionlimit(10**7)


def solution(maps):
    answer = []

    maps = [list(item) for item in maps]
    n, m = len(maps), len(maps[0])

    def dfs(x, y):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        cnt = int(maps[x][y])
        maps[x][y] = "X"
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != "X":
                cnt += dfs(nx, ny)

        return cnt

    for i in range(n):
        for j in range(m):
            if maps[i][j] != "X":
                answer.append(dfs(i, j))

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