[Algorithm/Swift] 프로그래머스(Lv.2) - 무인도 여행

안녕하세요 제인입니다!

프로그래머스에 최근 추가된 연습문제 중 하나인 무인도 여행이라는 문제를 풀어보았는데요,

문제 해결 아이디어를 코드로 구현하는 것이 꽤나 어려웠던 문제이기도 하고, Swift 풀이가 아직 없는 것 같아서 한 번 정리해보려고 합니다!

무인도에 왜 굳이 여행을 가는지는 모르겠지만 암튼 시작해볼게요..ㅎ

문제 링크

프로그래머스

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 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]

입출력 예 설명

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

연결된 땅들의 값을 합치면 다음과 같으며

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

 

입출력 예 #2

위 문자열은 다음과 같은 지도를 나타냅니다.

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

문제 풀이

입출력 예시가 그림으로 잘 설명이 되어있어 문제를 빨리 이해할 수 있었습니다.

이 문제의 핵심은 지도에서 연결되는 땅을 찾는 것인데요, 연결된 땅을 찾는 방법으로 DFS 알고리즘이 적합할 것 같다는 생각이 들었습니다.

제가 DFS 알고리즘을 적용해 문제를 풀이한 과정은 다음과 같습니다.

 

1. 주어진 maps 배열을 [[Int]] 타입의 2차원 배열로 만들기

maps 배열은 [String] 타입으로 주어지는데요, 지도를 순회하면서 탐색하기 위해서는 maps[i] 또한 배열로 바꾸어 전체 지도가 2차원 배열 형태가 될 수 있도록 하여 2차원 배열의 인덱스를 좌표값으로 이용해 탐색하는 것이 좋겠다는 생각이 들었고, 어차피 구해야 하는 값은 연결된 땅의 숫자를 더한 결과값들이기 때문에 연산이 쉽도록 maps[i]를 [Int]타입으로 변환해주었습니다. (무인도에 들어가는 숫자는 1~9이기 때문에 지도에서 바다를 나타내는 'X'는 0으로 변환해주었습니다.)

 

2. 방문 여부를 저장하기 위한 [[Bool]] 타입의 visited 배열 만들기

지도를 dfs함수를 통해 탐색하게 될텐데, 이 탐색 과정에서 인접한 모든 무인도를 방문하고 방문한 무인도의 값의 합을 result에 삽입하게 됩니다. 이 과정에서 이미 방문한 좌표인지 아닌지 방문 여부를 저장하기 위한 배열이 필요하기 때문에 1에서 만든 2차원 배열과 동일한 크기의 [[Bool]] 타입의 visited 배열을 만들어 줍니다.

 

3. dfs 함수 만들기 

지도를 순회하며 인접한 모든 무인도를 방문하고 무인도의 원소의 값의 합을 리턴해주는 dfs 함수를 만들어줍니다.

dfs 함수는 현재 좌표에서 상하좌우로 이동하며 무인도를 차례로 방문하며, 방문하지 않은 인접한 무인도가 더 이상 없을 경우 종료됩니다.

 

4. 지도 순회하며 result 값 계산하기

dfs 함수의 호출을 통해 지도를 순회하며 반환 값을 저장합니다.

Swift 풀이 코드

import Foundation

var mapArr = [[Int]]()
var visited = [[Bool]]()

func solution(_ maps: [String]) -> [Int] {
    var result: [Int] = []
    mapArr = Array(repeating: [], count: maps.count)
    visited = Array(repeating: Array(repeating: false, count: maps[0].count), count: maps.count)
    
    // maps [[Int]] 타입으로 바꾸기
    for i in 0..<maps.count {
        for j in maps[i] {
            if j == "X" {
                mapArr[i].append(0)
            } else {
                mapArr[i].append(Int(String(j))!)
            }
        }
    }
    
    // 지도 순회
    for i in 0..<mapArr.count {
        var sum = 0
        for j in 0..<mapArr[i].count {
            sum = dfs(i, j, &visited, mapArr)
            if sum > 0 {
                result.append(sum)
            }
        }
    }

    return result.isEmpty ? [-1] : result.sorted(by: <)
}

// 연결된 땅들의 원소를 더한 값을 반환하는 함수
func dfs(_ i: Int, _ j: Int, _ visited: inout [[Bool]], _ arr: [[Int]]) -> Int {
    
    // 지도 영역 벗어나거나 이미 방문한 좌표이거나 바다인 경우 종료
    if i < 0 || j < 0 || i >= visited.count || j >= visited[0].count
        || visited[i][j] || arr[i][j] == 0 { return 0 }
    
    visited[i][j] = true // 방문 처리
    
    return arr[i][j] + dfs(i-1, j, &visited, mapArr) + dfs(i+1, j, &visited, mapArr) + dfs(i, j-1, &visited, mapArr) + dfs(i, j+1, &visited, mapArr)
}

 

위의 문제 풀이 과정을 Swift 코드로 구현하면 위와 같습니다.

문제를 해결하고 나니 dfs 알고리즘을 활용한 전형적인 탐색 문제 같다는 생각이 드는데요, 아이디어를 코드로 옮기는 과정이 쉽지 않았던 것 같아 그래프 탐색 문제를 많이 연습해야겠다는 생각이 드네요🥲

 

그리고 dfs 함수에서 파라미터로 받은 visited 배열의 값을 변경하기 위해 inout 키워드를 사용해주었는데요, 

Value 타입의 값을 Reference 타입의 값처럼 참조로 전달하고 싶을 때 사용하는 파라미터인 In-Out Parameters에 대해서도 나중에 한번 정리해보도록 하겠습니다!!