[프로그래머스] 무인도 여행

문제

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

풀이

bfs를 활용한 풀이
바다가 아니고 방문하지 않은 곳을 시작으로 bfs를 실행한다.

시작 위치를 queue에 넣고 방문처리 및 값을 sum에 누적한다.
queue에서 위치를 하나 빼고 해당 위치에서 상하좌우를 확인한다.
만약 다음 위치가 섬이고 방문하지 않은 곳이면 queue에 넣는다.
이 것을 queue가 빌때 까지 반복한다.

sum을 answer에 더한다.

모든 곳을 확인 다 했다면 answer을 정렬한 값을 반환한다.
만약 answer가 비어있다면 [-1] 을 반환한다.

from collections import deque

def solution(maps):
    answer = []
    col = len(maps[0])
    row = len(maps)
    visited = [[False] * col for _ in range(row)]
    dq = deque([])
    
    def bfs(y,x,row,col):
        dy = [0,0,-1,1]
        dx = [-1,1,0,0]
        sum = 0
        queue = deque([(y,x)])
        visited[y][x] = True
        
        while queue:
            cur_y, cur_x = queue.popleft()
            sum += int(maps[cur_y][cur_x])
            for i in range(4):
                next_y = cur_y + dy[i]
                next_x = cur_x + dx[i]
              
                if 0 <= next_y < row and 0 <= next_x < col and maps[next_y][next_x] != "X" and not visited[next_y][next_x]:
                    queue.append((next_y,next_x))
                    visited[next_y][next_x] = True
          

        answer.append(sum)
            
    for y in range(row):
        for x in range(col):
            if maps[y][x] != "X" and not visited[y][x]:
                bfs(y,x,row,col)
       
    return sorted(answer) if len(answer) else [-1]