[Python] 프로그래머스 Lv2. 무인도 여행

문제

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

프로그래머스

문제 요약

x 또는 1~9 사이의 자연수가 칸마다 들어오는데, 숫자가 있는 칸이 연결될때는 하나의 무인도로 치고 각 칸에 있는 숫자를 식량의 양이라고 할때 오름차순으로 식량 개수를 출력하는 문제.
이때 x는 바다.

---

풀이

bfs를 이용해서 dx, dy로 방문하지 않았던 본인 근처를 계속 연결하고 식량의 개수를 더해가면 되는 문제다.

이때 중요한 부분은 숫자를 찾는 걸 먼저하고 이후에 좌우위아래를 다 확인하는 방식으로 진행하면 된다!

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    answer = []

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

    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'X' or visited[i][j]:
                continue

            queue = deque([(i, j)])
            visited[i][j] = True
            total = 0

            while queue:
                x, y = queue.popleft()
                total += int(maps[x][y])

                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if 0 <= nx < n and 0 <= ny < m:
                        if maps[nx][ny] != 'X' and not visited[nx][ny]:
                            visited[nx][ny] = True
                            queue.append((nx, ny))

            answer.append(total)

    return sorted(answer) if answer else [-1]

시간복잡도

최대 모든 칸을 한 번씩 방문하니까 O(n*m)
마지막에 정렬까지 하니까 섬의 개수를 k라고 할때 O(k log k)
그래서 정리하면 O(n*m+k log k) 일 것 같다.