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

문제

---

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

프로그래머스

• 소요 시간 : 30분
• 난이도 : LV 2

나의 풀이

---

 

접근 방법

BFS의 정석과도 같은 문제

맵을 전체적으로 돌면서 숫자이고 방문하지 않았다면 BFS를 사용해 이어진 영역의 합을 구한다. 

 

시간복잡도

 

이중 for 루프에서 모든 셀을 탐색하고, BFS로 연결된 모든 셀을 한 번씩만 방문하므로,

전체 시간 복잡도는 O(n * m)이다. (n <= 100, m <= 100)

 

코드

from collections import deque

def solution(maps): 
    answer = []
    
    # n 세로 * m 가로
    n = len(maps)
    m = len(maps[0])
    
    # 방문 체크 
    visited = [[False] * m for _ in range(n)]
    
    def bfs(y, x):
        q = deque()
        q.append((y, x))
        visited[y][x] = True 
        # 머물 수 있는 일수
        days = 0
        
        while q:
            cy, cx = q.popleft()
            days += int(maps[cy][cx])
            
            for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ny, nx = cy + dy, cx + dx
                if 0 <= ny < n and 0 <= nx < m:
                    if maps[ny][nx] == 'X' or visited[ny][nx]:  
                        continue 
                    q.append((ny, nx))
                    visited[ny][nx] = True 
        
        return days 
    
    
    for y in range(n):
        for x in range(m):
            if maps[y][x] == 'X' or visited[y][x]:
                continue
            answer.append(bfs(y, x))
    
    if answer:
        answer.sort()
    else:
        answer.append(-1)
    
    return answer

 

결과 : 정답

정리

---

 

쉬운 문제~