[BFS] 무인도 여행

무인도 여행

프로그래머스

 

from collections import deque

def bfs(i,j,n,m,visited,graph):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    
    queue=deque()
    queue.append((i,j))
    visited[i][j]=True
    tmp=int(graph[i][j])
    
    while queue:
        x,y=queue.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            
            if nx<0 or ny<0 or nx>=n or ny>=m: continue
            if graph[nx][ny]=='X': continue
            if visited[nx][ny]==True: continue
            visited[nx][ny]=True
            tmp+=int(graph[nx][ny])
            queue.append((nx,ny))
        
    return tmp

def solution(maps):
    answer = []
    
    n=len(maps)
    m=len(maps[0])
    
    graph=[]
    for map in maps:
        graph.append(list(map.rstrip()))
    
    visited=[[False for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j]=='X': continue
            if visited[i][j]==True: continue
            answer.append(bfs(i,j,n,m,visited,graph))
    
    if answer:
        answer.sort()
    else:
        answer.append(-1)
    return answer