본문 바로가기

알고리즘

(라이캣의 꿈-1) 출항 준비!

Best 20 · 14번Lv. 3그래프 탐색(BFS·DFS)

(라이캣의 꿈-1) 출항 준비!

해골섬으로 출항하는 캣

문제 설명

라이캣은 과거 사자탈을 쓰기 이전 해골섬 출항 꿈을 꾸었습니다.

캣은 매일 물고기를 잡기 위해 해골섬으로 향합니다. 해골섬은 위니브 월드에서 가장 물고기가 많이 잡히는 곳이지만, 그만큼 암초도 많고 안개도 자욱해서 위험한 곳으로 알려져 있습니다. 매일 아침 위니브 뉴스에서 안개가 걷히는 지역에 대한 정보를 전달하고 있습니다. 캣은 매일 아침 뉴스를 통해 지도를 확인하고 물고기를 잡기 위한 계획을 세웁니다.

"오늘은 얼마나 잡힐까냥?"

해골섬의 지도는 n x m 크기로 1 x 1 크기의 격자로 이뤄져 있습니다. 지도의 바깥은 안개가 자욱하기 때문에 나갈 수 없으며, 상하좌우 인접한 칸으로만 이동할 수 있습니다. 각 칸에는 숫자와 '#'이 표시됩니다. 숫자는 해당 칸에서 잡을 수 있는 물고기의 수를 나타내며, 캣이 자유롭게 이동할 수 있습니다. '#'으로 표시된 곳은 암초가 있어서 지나갈 수 없습니다.

캣은 (1, 1)에서 출발하여 (n, m)의 출구로 이동하며 최대한 많은 수의 물고기를 잡으려고 합니다. 지도 정보가 주어질 때, 캣이 이동하며 잡을 수 있는 모든 물고기의 수를 반환하는 함수를 작성해주세요. 만약 (1, 1)에서 (n, m)까지 경로가 없는 경우에는 -1을 반환합니다.


제한 사항

  • 지도는 n x m 크기의 2차원 배열로, '#' 또는 0 이상의 정수로 이뤄져 있습니다.
    • '#'은 암초로 지나갈 수 없습니다.
    • 0 이상의 정수는 이동할 수 있는 바다를 뜻하며, 잡을 수 있는 물고기의 수를 의미합니다.
  • 2 ≤ n, m ≤ 1,000

입출력 예

입력출력
[[1, 3, '#'], [0, '#', 2], [0, 1, 1]]8
[[0, '#', 1, 0], [2, 1, 1, 2], ['#', 3, 0, 1], [1, '#', '#', 3], [0, 2, '#', 1]]15
[[1, '#', 1], [2, 1, '#'], ['#', '#', 0], [1, '#', 1]]-1

입출력 설명

  • (1, 1)에서 갈 수 있는 모든 칸의 물고기를 더합니다. 출구로 가는 길 위에 있지 않은 칸이라도 들렀다 돌아올 수 있으면 더합니다.
  • (1, 1)부터 (n, m)까지 경로가 없는 경우에는 -1을 반환합니다.
  • 같은 칸을 여러 번 지나갈 수 있지만, 한 칸의 물고기는 한 번만 셉니다.

예시 테스트

#입력기대값
1[[1, 3, "#"], [0, "#", 2], [0, 1, 1]]8
2[[0, "#", 1, 0], [2, 1, 1, 2], ["#", 3, 0, 1], [1, "#", "#", 3], [0, 2, "#", 1]]15
3[[1, "#", 1], [2, 1, "#"], ["#", "#", 0], [1, "#", 1]]-1

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.