[프로그래머스] 무인도 여행(LV 2 - Python)

무인도 여행

해당 글에서는 무인도 여행 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

🔷 문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

 

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

 

해당 문제를 읽으면 BFS, DFS 문제라는 것을 알 수 있을 것이다. 무인도에서 상화좌우 이동을 하여 인접한 무인도를 모두 탐색해야 하기 때문이다. 

BFS를 이용해 무인도 여행 문제를 풀이하자.

 

🔷 문제 풀이

BFS를 이용하기 위한 방문 여부를 나타내는 visited 리스트를 생성해야 한다.

또 상화좌우 탐색을 위한 배열인 dx, dy를 생성한다.

 

이후 deque를 이용해 그래프 전체에 걸쳐 BFS를 진행한다. 이때 이미 방문했거나 (r, c)에 위치한 값이 숫자가 아닌 경우 탐색해선 안 된다.

인접한 무인도가 있는 경우 반복문을 통해 BFS를 계속 진행한다.

 

🔷 코드

BFS를 이용해 해당 문제를 풀이한 코드는 다음과 같다.

from collections import deque

def solution(maps):
    
    ans = []
    visited = [[False]*len(maps[-1]) for _ in range(len(maps))]
    graph = [[0]*len(maps[-1]) for _ in range(len(maps))]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    N, M = len(maps), len(maps[-1]) # row, col
    for r in range(N):
        for c in range(M):
            if maps[r][c] == 'X':
                continue
            graph[r][c] = int(maps[r][c])
    
    for r in range(N):
        for c in range(M):
            if not visited[r][c] and graph[r][c]: # 방문 no, 남은 일수 > 0
                que = deque([(r,c)])
                cnt = graph[r][c]
                visited[r][c] = True
                while que:
                    x, y = que.popleft()
                    for d in range(4):
                        nx = x + dx[d]
                        ny = y + dy[d]
                        if 0<=nx<N and 0<=ny<M and graph[nx][ny] and not visited[nx][ny]:
                            que.append((nx,ny))
                            cnt += graph[nx][ny]
                            visited[nx][ny] = True
                ans.append(cnt)
    
    if len(ans):
        ans.sort()
    else: # 무인도가 없는 경우
        ans.append(-1)
        
    return ans