import sys
sys.setrecursionlimit(10 ** 4)
def dfs(row, col, food):
n = len(grid)
m = len(grid[0])
delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
food += int(grid[row][col])
for i in range(len(delta)):
delta_row, delta_col = delta[i]
new_row = row + delta_row
new_col = col + delta_col
if new_row < 0 or new_row >= n or new_col < 0 or new_col >= m:
continue
if grid[new_row][new_col] == 'X':
continue
if not visited[new_row][new_col]:
visited[new_row][new_col] = True
food = dfs(new_row, new_col, food)
return food
def solution(maps):
global visited
global grid
answers = []
answer = 0
n = len(maps)
m = len(maps[0])
visited = [[False] * m for _ in range(n)]
grid = list(map(list, maps))
for i in range(n):
for j in range(m):
if grid[i][j] != 'X' and not visited[i][j]:
visited[i][j] = True
answers.append(dfs(i, j, answer))
if not answers:
answers.append(-1)
answers.sort()
return answers
문제 정의
여러 섬들의 식량의 합들을 각각 구해서 정렬하는 문제이다.
시간복잡도 계산
모든 노드들을 탐색했을 때 최대 10,000개 노드를 탐색하기 때문에 충분히 시간내에 통과할 것이라 생각했다.
문제 풀이
입력의 크기가 N <= 100, M <= 100으로 크지 않기 때문에 모든 노드들을 탐색하기로 하고 DFS를 수행하여 연결된 섬들을 구분한 뒤 식량값들을 더해서 반환하는 식으로 풀었다.
예외 사항
기타 예외 사항 없음.