[프로그래머스 Lv. 2] 무인도 여행

문제

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

접근

1) maps에서 연결되어 있는 부분 (한 번의 그래프 탐색으로 접근이 가능한 영역들)을 Connected Component로 본다.

2) maps를 완전탐색하면서 maps의 원소가 X가 아니고 방문하지 않은 곳에 대해서 그래프 탐색을 진행한다.

3) 탐색을 하면서 연결 되어 있는 원소들에 대해 값을 더하고 탐색이 끝나면 그 값을 반환한다.

Code

from collections import deque

dy, dx = [1, 0, -1, 0], [0, 1, 0, -1]

def solution(maps):
    h, w = len(maps), len(maps[0])
    answer = []
    visit = [[False] * w for _ in range(h)]

    def bfs(y, x):
        q = deque()
        q.append((y, x))
        ret = int(maps[y][x])

        while q:
            curr_y, curr_x = q.popleft()

            for i in range(4):
                next_y, next_x = curr_y + dy[i], curr_x + dx[i]

                if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                    continue

                if maps[next_y][next_x] != 'X' and not visit[next_y][next_x]:
                    q.append((next_y, next_x))
                    visit[next_y][next_x] = True
                    ret += int(maps[next_y][next_x])
        return ret

    for y in range(h):
        for x in range(w):
            if maps[y][x] != 'X' and not visit[y][x]:
                visit[y][x] = True
                land = bfs(y, x)
                answer.append(land)
    return sorted(answer) if answer else [-1]