프로그래머스 - 무인도 여행(DFS, BFS) / Level 2 / Python

문제 📋

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

풀이 📝

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

1. 문제 정의
   여러 섬들의 식량의 합들을 각각 구해서 정렬하는 문제이다.
   

2. 시간복잡도 계산
   모든 노드들을 탐색했을 때 최대 10,000개 노드를 탐색하기 때문에 충분히 시간내에 통과할 것이라 생각했다.

3. 문제 풀이
   입력의 크기가 N <= 100, M <= 100으로 크지 않기 때문에 모든 노드들을 탐색하기로 하고 DFS를 수행하여 연결된 섬들을 구분한 뒤 식량값들을 더해서 반환하는 식으로 풀었다.

4. 예외 사항
   기타 예외 사항 없음.