[Algorithm] 무인도 여행

[hwangJi-dev]

💬 문제

[코딩테스트 연습 - 무인도 여행](https://school.programmers.co.kr/learn/courses/30/lessons/154540)

💬 Idea

1. 지도를 2차원 배열로 만들어준다.
2. 방문 여부를 저장하기 위해 지도와 같은 크기의 Bool형 2차원 배열을 만든다.
3. 지도를 돌며 방문하지 않은 1~9 사이의 자연수를 가진 땅일 때 재귀함수를 호출한다.

🔑 <재귀함수 설계>

- 출발 좌표로부터 상, 하, 좌, 우 좌표를 계산해준다.
    - 이 때 좌표의 상 하 좌 우 에서 방문할 수 있는 최소 최대값을 유념하여 처리해준다. (Index out of Range 방지)
- 출발 좌표를 방문 처리해준다.
- 이후 방문되지 않았고, 좌표값이 정수값인 상하좌우 좌표를 돈다
- 재귀함수가 끝날 때까지 방문한 좌표의 정수값을 sum에 더한다.

1. 재귀함수를 호출한 후 도출된 sum이 연결된 땅들의 총합을 의미하므로 ans에 append해준다.
2. 3~4를 반복
3. ans가 빈 배열일 경우 [-1]을 리턴하고, 그렇지 않다면 오름차순으로 정렬하여 리턴한다.

💬 풀이

var visited: [[Bool]] = []
var sum = 0

func solution(maps:[String]) -> [Int] {
    var ans: [Int] = []
    var mapArr: [[String]] = []
    
    // String에서 좌표값을 처리하기 위해 지도를 2차원 배열로 만든다
    maps.forEach({ mapArr.append(Array($0).map({ String($0) })) })

    // 방문 여부를 저장하기 위해 mapArr과 같은 크기의 Bool형 2차원 배열을 만든다
    visited = Array(repeating: Array(repeating: false, count: maps[0].count), count: maps.count)
    
    // 지도를 돌며 
    for (i, col) in mapArr.enumerated() {
            for (j, row) in col.enumerated() {
	        // 방문하지 않은 땅일 때 
                if row != "X" && visited[i][j] == false {
                    // 해당 땅에서 연결된 땅의 총합을 알기 위해 dfs 메서드 호출
                    dfs(index: (i, j), maps: mapArr)
                    // 연결된 땅의 총합을 ans에 append
                    ans.append(sum)
                    // sum 0으로 초기화
                    sum = 0
                }
            }
        }
    
    return ans == [] ? [-1] : ans.sorted()
}

func dfs(index: (Int, Int), maps: [[String]]) {
    let u = (index.0 - 1 < 0 ? index.0 : index.0 - 1, index.1) // 상
    let d = (index.0 + 1 >= maps.count ? index.0 : index.0 + 1, index.1) // 하
    let l = (index.0, index.1 - 1 < 0 ? index.1 : index.1 - 1) // 좌
    let r = (index.0, index.1 + 1 >= maps[0].count ? index.1 : index.1 + 1) // 우
    
    // 방문 처리
    visited[index.0][index.1] = true 
    
    // 방문되지 않았고, 좌표값이 정수값인 상하좌우 좌표를 돈다
    for point in [u, d, l, r] {
        if visited[point.0][point.1] == false && maps[point.0][point.1] != "X" {
            dfs(index: (point.0, point.1), maps: maps)
        }
    }
    
    // sum에 방문한 좌표의 값을 더한다
    sum += Int(maps[index.0][index.1])!
}