[프로그래머스] 154540. 무인도 여행 | BFS | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• 바다와 무인도의 식량 개수를 담고있는 지도가 주어진다. 'X'는 바다이고 1~9 숫자가 적힌 곳은 무인도가 있는 곳이다.
• 상하좌우로 인접한 무인도들은 하나의 무인도이다.
• 무인도에 존재하는 식량의 합만큼 무인도에 머무를 수 있다.
• 각 무인도마다 머무를 수 있는 최대날짜를 구하고 오름차순으로 정렬하라.

---

문제 조건

• 만약 무인도가 없다면 배열에 -1을 담아 리턴하라 
• 지도는 직사각형 형태이다

---

시행착오

bfs로 풀 수 있는 문제임을 바로 알았다. 나 bfs 이제 좀 잘하는듯 ㅎ

---

접근방법

• BFS로 연결된 노드들의 합을 구해서 answer에 추가한다.

---

소스코드

from collections import deque

def solution(maps):
    answer = []
    N, M = len(maps), len(maps[0])
    visited = [[False]*M for _ in range(N)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    def get_sum_of_days(start_x, start_y):
        visited[start_x][start_y] = True
        cnt = 0

        q = deque([(start_x, start_y)])
        while q:
            x, y = q.popleft()
            cnt += int(maps[x][y])

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < N and 0 <= ny < M) and maps[nx][ny] != 'X':
                    if not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx, ny))

        return cnt

    for i in range(N):
        for j in range(M):
            if maps[i][j] != 'X' and not visited[i][j]:
                answer.append(get_sum_of_days(i, j))

    if not answer:
        answer.append(-1)
    else:
    	answer.sort()

    return answer