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

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/154540?language=swift

프로그래머스

 

N*M크기의 격자판이 있다고 합시다 (지도를 의미).

- 각 칸에는 X (바다) 혹은 1~9사이의 자연수( 각 칸의 무인도에 있는 식량 수)가 적혀져 있음.

- 상하좌우로 연결되어 있는 칸끼리는 하나의 무인도임.

- 하나의 무인도 땅에 있는 식량의 합은 그 무인도에 머물 수 있는 기간(일)을 의미

- 지도에 0개 이상의 무인도가 있을 때, 각 무인도에 머물 수 있는 기간을 오름차순 배열로 출력하는 문제

 

접근방법

1. N*M 지도를 순회하면서 무인도를 찾는다.

1.1 무인도인 칸을 발견하면, 그 칸과 연결된 모든 무인도 칸을 순회하며, 그 무인도에 있는 식량의 합을 구한다. -> 구한 값을 result 배열에 추가

2. result배열에 원소가 있으면, 정렬해서 출력, 없으면 -1을 담아 출력

 

1.1 부분은 DFS를 Stack(배열로 만듦)을 써서 풀이했다.

같은 곳을 또 방문하면 안되니까 visit배열을 사용했고, 처음 무인도 칸은 while문 밖에서 true로 표시해줬지만,

stack에 넣을 때 visit = true로 표시해줬다.

 

이번엔 새로 방문할 칸이 격자칸 내에 있는 칸인지 확인하는 부분을 0..<R ~= nr && 0..<C ~= nc

~= 범위 연산자를 사용했다. 

범위 ~= 숫자 : 이렇게 사용하면 숫자가 범위에 포함되면 true, 아니면 false를 리턴한다.

 

DFS는 보통 재귀함수를 사용해서 풀이했었는데, Stack을 사용해서 앞에서 원소를 빼는 방식으로 동작하게 하지 않고 (BFS처럼) 뒤에서 부터 원소를 빼서 동작하게 하면 DFS로도 구현이 가능하다는걸 알게 돼서 이번에 써먹어봄!

 

아, 그리고 고차함수 map에서 $0 를 쓰지 않는 경우는 _ in 을 꼭 해줘야 했다.

그리고 Character는 Int(Character)이 안돼서 Int(String)으로 쓰기 위해.. Int(String(Character)) 이런 식으로 함..

 

소스코드

import Foundation

func solution(_ maps:[String]) -> [Int] {
    
    let cmaps:[[Character]] = maps.map{ Array($0) }
    
    let dr = [0,0,1,-1]
    let dc = [1,-1,0,0]
    let R = maps.count
    let C = maps[0].count
    
    var visit:[[Bool]] = cmaps.map{ $0.map { _ in false } }
    var result:[Int] = []
    
    for r in 0..<R {
        for c in 0..<C {
            if !visit[r][c] && cmaps[r][c] != "X" {
                // 1. 무인도 발견
                var stack:[(Int,Int)] = [(r,c)]
                visit[r][c] = true
                var sumOfFood:Int = 0
                
                // 1.1 식량 합 계산 (DFS)
                while !stack.isEmpty {
                    let now = stack.removeLast() // 최근에 방문한 곳(담은 곳) 부터 탐색 : DFS
                    sumOfFood += Int(String(cmaps[now.0][now.1]))!
                    for i in 0..<4 {
                        let nr = now.0 + dr[i]
                        let nc = now.1 + dc[i]
                        if 0..<R ~= nr && 0..<C ~= nc 
                        && cmaps[nr][nc] != "X" 
                        && !visit[nr][nc] {
                            visit[nr][nc] = true
                            stack.append((nr,nc))                            
                        }
                    }
                }
                result.append(sumOfFood)
            }
        }
    }
    
    
    return result.isEmpty ? [-1] : result.sorted()
}