[프로그래머스 / 파이썬] 무인도 여행

프로그래머스 2레벨 문제이다.

문제 주소: https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

문제 해석

기본적인 블러드 필 문제이다. 섬의 영역에 숫자가 주어지는데 해당 숫자를 모두 더한 값이 무인도에서 살아남을 수 있는 기간이 된다.
모든 무인도의 머물 수 있는 기간을 오름차순으로 반환하는 문제이다.

문제 풀이

먼저 쉽게 이동하도록 하기 위해 1차원 형태의 maps를 2차원 형태로 변형해 주었다.

bfs를 통해 블러드 필로 구역을 탐색하였고, 머물 수 있는 날짜를 모두 더해주어 반환해 주었다.

문제 코드

from collections import deque
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]

def island(maps, i, j, n, m, visit):
    visit[i][j] = 1
    q = deque()
    q.append([i, j])
    days = 0
    while q:
        i, j = q.popleft()
        days += int(maps[i][j])
        for d in range(4):
            x, y = i + dx[d], j + dy[d]
            if not(0 <= x < n and 0 <= y < m): continue
            if visit[x][y] == 0 and maps[x][y] != 'X':
                q.append([x, y])
                visit[x][y] = 1
    return days

def solution(maps):
    answer = []
    for i in range(len(maps)):
        maps[i] = list(maps[i])
    n = len(maps)
    m = len(maps[0])
    visit = [[0] * m for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 'X' and visit[i][j] == 0:
                answer.append(island(maps, i, j, n, m, visit))
    if answer:
        return sorted(answer)
    else:
        return [-1]

문자열 형태로 저장되므로 이 부분만 조심해서 머물 수 있는 날의 총합을 구하면 된다.