문제 링크

풀이

모든 노드를 탐색하며 숫자 노드일 때만 BFS를 돌려 식량 개수를 알아낸다.

예를 들어, 좌상부터 우하까지 탐색을 진행하면

5를 최초 발견하여 5+9+1+...+1 = 27을 정답 리스트에 추가.

1을 발견하여 1을 정답 리스트에 추가.

또 1을 발견하여 1을 정답 리스트에 추가.

그렇게 해서 answer = [27,1,1]이 되고

이를 정렬하여 최종 정답 반환을 한다.

리스트가 비었다면 [-1]을 리턴.

코드

from collections import deque

def bfs(a,b,visited,n,m,maps):
    q = deque([(a,b)])
    visited[a][b] = True
    cnt = int(maps[a][b])
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and maps[nx][ny].isdigit():
                q.append((nx,ny))
                visited[nx][ny] = True
                cnt += int(maps[nx][ny])
    return cnt,visited
        

def solution(maps):
    answer = []
    n = len(maps)
    m = len(maps[0])
    visited = [[False]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if maps[i][j].isdigit() and not visited[i][j]:
                cnt, visited = bfs(i,j,visited,n,m,maps)
                answer.append(cnt)
    if answer:
        answer.sort()
    else:
        answer = [-1]
    return answer