[프로그래머스 - Python] 154540 - 무인도 여행

0.  문제 링크

 

 

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

프로그래머스

---

1.  풀이 방법

 

 

1. 이중 for loop를 사용하여, 모든 맵을 훑는다.
2. 이때 무인도인데, 방문한 적이 없다면 BFS를 통해 연결된 무인도를 찾고, 먹을 수 있는 모든 음식을 찾는다.
3. 이를 append 하고, 반환은 정렬해서 반환하도록 한다.

---

2.  코드

 

 

from collections import deque

def solution(maps):
    def bfs(y, x):        
        food = int(maps[y][x])     # 무인도의 음식들
        dq = deque([(y, x)])
        check[y][x] = True
        
        while dq:
            y, x, = dq.popleft()
            for dy, dx in dir:
                ny, nx = y + dy, x + dx
                if 0 <= ny < h and 0 <= nx < w:
                    if maps[ny][nx] != 'X':
                        if not check[ny][nx]:
                            food += int(maps[ny][nx])
                            dq.append((ny, nx))
                            check[ny][nx] = True
        return food               
        
    answer = []
    
    h = len(maps)
    w = len(maps[0])
    check = [[False] * w for _ in range(h)]
    dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for y in range(h):
        for x in range(w):
            if maps[y][x] != 'X' and not check[y][x]:
                answer.append(bfs(y, x))        # 바다가 아니고, 방문한 적이 없으면 bfs 실행
    
    if answer:
        answer.sort()
    else:
        answer.append(-1)
    return answer

---

3.  마무리