[Programmers] 무인도 여행 - 154540

728x90

BFS 문제..!!! BFS 지금 3번째 틀리는 건데.. 조만간 복습으로 다시 풀어야겠다.

 

Question

 

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

 

Code

 

from collections import deque
def solution(maps):
    answer = []
    directions = [(-1,0),(1,0),(0,-1),(0,1)] 
    rows, cols = len(maps), len(maps[0])
    grid = [list(row) for row in maps]
    
    def bfs(x, y):
        queue = deque([(x, y)])
        score = int(grid[x][y])
        grid[x][y] = 'X'
        
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x+dx, y+dy
                if 0<=nx<rows and 0<=ny<cols and grid[nx][ny]!='X':
                    queue.append((nx, ny))
                    score += int(grid[nx][ny])
                    grid[nx][ny] = 'X'
        
        return score
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] != 'X': answer.append(bfs(i,j))
    
    
    return sorted(answer) if answer else [-1]

 

now me

On my github