[programmers] Lv.2 무인도 여행 (python)

✏️ 문제

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

 

🤖 알고리즘

 

#BFS  #DFS  

 

 

🤯 풀이 방법

 

전형적인 BFS / DFS 문제

visited 배열을 이용해서 방문하지 않은 시작점을 찾고, 끝까지 탐색하며 방문한 지점의 숫자들을 더한다

이때 방문하면 원래 리스트의 값을 X로 바꿔주는데 그 순서를 잘못하면 재방문할 수도 있으니 주의

 

👾 구현 코드 (파이썬)

from collections import deque

def solution(maps):
    def travel(i, j):
        stay = int(newmap[i][j])
        q = deque()
        q.append([i, j])
        V[i][j] = 1

        di = [0, 1, 0, -1]
        dj = [1, 0, -1, 0]

        while q:
            ii, jj = q.popleft()
            for k in range(4):
                ni, nj = ii + di[k], jj + dj[k]
                if 0 <= ni < h and 0 <= nj < w and V[ni][nj] == 0 and newmap[ni][nj] != 'X':
                    q.append([ni, nj])
                    V[ni][nj] = 1
                    stay += int(newmap[ni][nj])
                    newmap[ni][nj] = 'X'	# 다시 방문하지 않게 값 변경
    
        return stay
    
    answer = []
    h = len(maps)   # 세로 길이
    w = len(maps[0])    # 가로 길이
    newmap = []
    for m in maps:
        newmap.append(list(m))
    
    V = [[0] * w for _ in range(h)]
    
    for i in range(h):
        for j in range(w):
        	# 아직 방문하지 않은 시작점 찾기
            if newmap[i][j] != 'X':
                answer.append(travel(i, j))
    
    return [-1] if len(answer) == 0 else sorted(answer)	# 가능한 경우 없는 예외 처리

 

 

프로그래머스