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

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

무인도 여행

---

문제 설명

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

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

---

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

---

입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

---

아이디어, 문제풀이

• 기본적인 그래프 탐색 문제
• 모든 그래프 탐색 문제는 아주 일부의 경우를 제외하고 dfs 로 풀 수 있다.
• 기본 dfs 틀을 머릿속에 그리고, 합을 구해주는 변수 + 수식을 적제적소에 적용하면 풀 수 있다.

---

TROUBLE SHOOTING

프로그래머스에서만 그런지는 잘 모르겠지만,

if 0<=nx<n and 0<=ny<m and visit[nx][ny] == 0 :
    visit[nx][ny] = 1
                      
    if graph[nx][ny] != 'X': 
        day += int(graph[nx][ny])
        stack.append((nx, ny))

전혀몰랐는데, 이 조건문에서

if visit[nx][ny] == 0 and 0<=nx<n and 0<=ny<m:

이렇게 visit을 먼저 조건문에 작성하면 index 에러가 난다…………. 사실 합당한 이유이긴 하다. nx, ny가 만약 범위에서 벗어나 입력이 된다면, visit 배열에 존재하지 않기에 list index에러가 나는게 당연한데, 2차원 배열 dfs 문제를 풀면서 깊게 신경쓰지 않아 생긴 문제였다.

파이썬에서는 if조건문이 and 로 엮여 있더라도, 앞에서부터 체크하기때문! 앞으론 조심하자.

---

코드

def solution(maps):
    answer = []
    # print(maps)
    n = len(maps)
    graph = []
    # print(maps[0])
    for i in range(n):
        graph.append(list(maps[i]))
    m = len(graph[0])
    visit = [[0] * m for _ in range(n)]
    # print(visit)
    

    def fun(a, b):
        
        stack = []
        stack.append((a,b))
        visit[a][b] = 1
        day = int(graph[a][b])
        
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]

        while stack:
            
            x,y = stack.pop()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]    
                
                if 0<=nx<n and 0<=ny<m and visit[nx][ny] == 0:
                    visit[nx][ny] = 1
                      
                    if graph[nx][ny] != 'X': 
                        day += int(graph[nx][ny])
                        stack.append((nx, ny))
                        
        answer.append(day)

        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] != 'X' and visit[i][j] == 0:
                fun(i, j)
    
    if len(answer) == 0:
        answer.append(-1)
    else:
        answer.sort()
    
    print(answer)    
    
    return answer