[Swift] 백준 미로 보수 30689

https://www.acmicpc.net/problem/30689

 

 

 

1. 문제이해

• 세로 N, 가로 M, N * M 크기의 미로
• 화살표를 따라 미로 범위 밖으로 나갈 수 있으면 탈출 성공
• 사이클의 경우 점프대를 설치하여 탈출할 수 있다.
• 미로의 어느 칸에서 시작하더라도 탈출할 수 있도록 만들자. 단, 최소한의 비용을 사용해 점프대를 설치해야 한다. 필요한 최소한의 비용을 구하자.

 

2. 접근방법

• dfs로 경로 탐색
• 이동 시 경로를 스택에 저장
• 이동 할 칸이 방문 했던 칸이라면 사이클 의심
• 스택에 저장된 경로대로 거꾸로 탐색하여 사이클 의심되는 칸을 도달할 경우 사이클, 최소 설치 비용 구하기

 

 

func solution(){
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let N = input[0]
    let M = input[1]
    var map = [[String]]() // 미로
    var cost = [[Int]]() // 점프대 설치 비용
    var visited = Array(repeating: Array(repeating: false, count: M), count: N)
    var stack = [(Int, Int)]() //
    
    var result = 0
    
    for _ in 0..<N{
        map.append(readLine()!.map{String($0)})
    }
    for _ in 0..<N{
        cost.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }
    
    func dfs(x: Int, y: Int){
        let arrow = map[x][y]
        var nextX = x
        var nextY = y
        
        if arrow == "L"{
            nextY -= 1
        }else if arrow == "R"{
            nextY += 1
        }else if arrow == "U"{
            nextX -= 1
        }else{ // D
            nextX += 1
        }
        
        if nextX >= 0, nextX < N, nextY >= 0, nextY < M {
            if visited[nextX][nextY] == false{ // 다음 칸이 방문하지 않은 칸이라면
                visited[x][y] = true
                stack.append((nextX, nextY)) // 스택에 경로 추가
                dfs(x: nextX, y: nextY)
                stack.removeLast()
            }else{
                // 다음 칸이 방문했던 칸이라면 사이클이 발생했다고 볼 수 있는데...
                // 스택에 저장된 경로대로 거꾸로 탐색, 최소 설치 비용 구하기
                // 탐색 중 사이클 발생 지점(현재 위치에서 다음 칸)에 도달한다면
                var minCost = Int.max
                for point in stack.reversed(){
                    minCost = min(minCost, cost[point.0][point.1])
                    if point.0 == nextX, point.1 == nextY{
                        result += minCost
                        break
                    }
                }
            }
        }
    }
    
    for i in 0..<N{
        for j in 0..<M{
            if !visited[i][j]{
                stack.append((i,j))
                dfs(x: i, y: j)
                stack.removeLast()
            }
        }
    }
    print(result)
}
solution()