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

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

프로그래머스

 

from collections import deque

def bfs(a, b, maps, visited):
    # 각 구역에 대한 값 저장
    dap = 0
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    N, M = len(maps), len(maps[0])
    
    dq = deque()
    dq.append((a, b))
    dap += int(maps[a][b])
    
    while dq:
        x, y = dq.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            # map안에 있고 방문하지 않았고 X가 아니면 더하기
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and maps[nx][ny] != 'X':
                visited[nx][ny] = 1
                dap += int(maps[nx][ny])
                dq.append((nx, ny))
    
    return dap

def solution(maps):
    answer = []
    N, M = len(maps), len(maps[0])
    visited = [[0]*M for _ in range(N)]
    
    for i in range(N):
        for j in range(M):
            # X가 아니고 아직 방문하지 않았으면 새로운 구역
            if maps[i][j] != 'X' and visited[i][j] == 0:
                visited[i][j] = 1
                answer.append(bfs(i, j, maps, visited))
            
    # 숫자가 있는 구역이 없으면 -1 반환
    if len(answer) == 0:
        answer.append(-1)
    # 구역이 있으면 정렬해서 반환
    else:
        answer.sort()
    return answer