[프로그래머스] Lv.2 무인도 여행 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/154540
• 🔑 BFS로 연결된 무인도를 탐색
  • maps를 순회하면서 무인도를 만나면('X'가 아닌 부분) 현재 위치에서 BFS 탐색을 실시
  • BFS를 시작하는 위치와 연결된 무인도들을 모두 탐색하면서 식량 개수를 카운트하고 'X'로 바꾼다.
  • BFS 종료 시 식량 개수를 리턴
  • 또 maps를 순회하면서 무인도를 찾고 BFS 탐색 반복

 

from collections import deque

def solution(maps):
    
    def bfs(x, y):
        mx, my = [0, 0, 1, -1], [1, -1, 0, 0]
        q = deque([(x, y)])
        food = int(maps[x][y])
        maps[x][y] = 'X'

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx, ny = x + mx[i], y + my[i]

                if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]) and maps[nx][ny] != 'X':
                    food += int(maps[nx][ny])
                    maps[nx][ny] = 'X'
                    q.append((nx, ny))

        return food

    answer = []
    
    for i in range(len(maps)):
        maps[i] = list(maps[i])
        
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] != 'X':
                answer.append(bfs(i, j))
    
    return [-1] if answer == [] else sorted(answer)