111. 무인도 여행

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

---

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

---

입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

---

입출력 예 설명

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

입출력 예 #2

위 문자열은 다음과 같은 지도를 나타냅니다.

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

 

 

정답코드:

# DFS 재귀함수로 구현했더니, 재귀함수 호출이 너무 많아 런타임 오류 뜸. 스택으로 변환해서 구현
# 설명은 재귀함수부분에 다 설명이 되어있기 때문에 따로 밑에 있는 부분에서는 주석추가 안했음.
# def solution(maps_by_str):
#     #마찬가지로 상하좌우 살펴보는 변수
#     maps = []
#     for i in maps_by_str:
#         maps.append(list(i))
#
#     dx = [0, 0, 1, -1]
#     dy = [1, -1, 0, 0]
#     #col, row 길이
#     m = len(maps)
#     n = len(maps[0])
#     answer = []
#
#     #섬 하나를 바다로 바꾸는 함수. 밑에 for문을 먼저보고 이 함수를 보면 이해가 빠릅니다.
#     def dfs_recursive(r, c):
#         # 방문한 노드의 상하좌우를 살피는데 배열에 크기에 벗어나거나, 육지가 아니면 스킵
#         if r < 0 or r >= m or c < 0 or c >= n or maps[r][c] == 'X':
#             return
#
#         # 식량 합계계산 및 방문처리
#         nonlocal sum_food
#         sum_food += int(maps[r][c])
#         maps[r][c] = 'X'
#         #상하좌우 살펴보다가 육지 발견하면 반복
#         for i in range(4):
#             dfs_recursive(r + dx[i], c + dy[i])
#         return
#
#     #전체 배열을 방문함
#     for r in range(m):
#         for c in range(n):
#             #node라는 빈 변수에 grid[r][c]가 X가 안나올때까지 스킵
#             node = maps[r][c]
#             if node == 'X':
#                 continue
#
#             #node에 1이 나와 저장하면 육지 발견. 섬 하나로 간주 후, 그 섬 하나를 바다로 바꿈
#             #섬 하나에서 버틸수 있는 시간 구하는 함수
#             sum_food = 0
#             dfs_recursive(r, c)
#             answer.append(sum_food)
#
#     if not answer:
#         return [-1]
#     return sorted(answer)
#
# print(solution(["XXX","XXX","XXX"]))


def solution(maps_by_str):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    maps = []
    answer = []
    for i in maps_by_str:
        maps.append(list(i))

    rows, cols = len(maps), len(maps[0])

    for row in range(rows):
        for col in range(cols):
            if maps[row][col] == 'X':
                continue
            sum_food = 0
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                if maps[x][y] != 'X':
                    sum_food += int(maps[x][y])
                maps[x][y] = 'X'
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or maps[nx][ny] == 'X':
                        continue
                    stack.append((nx, ny))
            answer.append(sum_food)

    if not answer:
        return [-1]
    return sorted(answer)

print(solution(["X591X","X1X5X","X231X", "1XXX1"]))