[백준/Swift] 2933: 미네랄

백준 2933 미네랄

2933번: 미네랄

BFS 문제 입니다.

 

간단한 문제 요약

  두 사람이 동굴(R,C크기) 양쪽에 서서 번갈아가면서 막대기를 던집니다. 맨 처음 좌 -> 우 그 다음 우-> 좌 의 반복으로 던집니다. 미네랄 "x" 에 맞을 경우 미네랄이 파괴가 되는데 분리된 클러스터(땅과 닿지 않거나, 땅과 연결된 클러스터로 부터 분리된 경우)인 경우 중력에 의해 바닥으로 떨어집니다. 떨어지는 동안 클러스터 모양은 변하지 않습니다. 

 

고려해야 할 사항

• 막대기는 특정 높이를 유지하며 날라간다. 이때 미네랄을 맞출 경우 해당 미네랄만 없어진다. 막대기도 없어진다.
• 불안정한 클러스터( 파괴된 미네랄로 인해 공중에 떠 있는 미네랄 집단)
• 불안정한 클러스터는 중력에 의해 아래로 떨어지는데 땅에 닿을 때 까지 or 타 클러스터 집단에 속한 특정 미네랄 위에 닿을 때 까지 떨어집니다.
• 두 개 이상의 클러스터가 동시에 떨어지지 않습니다.

문제 풀이, 했갈렸던 점

 막대를 모두 던질 때 까지 미네랄을 부수면서 부순 이후의 불안정한 클러스터를 파악하고 맵에서 지운 후 중력에 의해 떨어진 불안정한 클러스터를 맵에 다시 추가하는 방식으로 문제를 구현 했습니다. 원래 안정한 클러스터는 맵의 바닥에 안착된 형태입니다. 따라서 map을 탐색할 때 불안정한 클러스터는 bfs 탐색을 통해 맵의 바닥과 연결되지 않는 클러스터를 찾았습니다. 다행인건 이런 불안정한 클러스터가 딱 하나입니다. 단순하게 맵의 전체를 탐색할 때 현재 맵에 불안정한 클러스터가 있는지의 여부 체크와 이때 bfs를 통해 탐색한 불안정한 클러스터 좌표를 큐에 저장합니다. map에서 불안정한 클러스터를 전부 지웁니다. 이후 땅에 떨어질 때의 상황을 y값 + 1을 통해 바닥에 닿거나, 타 안정한 클러스터 위에 안착될 때까지 떨어트린 후 map에 다시 추가하는 방식의 반복으로 문제를 구현했습니다.

 

 문제를 풀며 했갈렸던 점은 클러스터가 떨어질 때의 좌표값에 대한 체크였습니다. 2차원 배열(map)로 동굴을 구현했습니다. 문제에서 주어지는 input 그대로 map 변수에 저장했습니다. 클러스터가 한 칸 떨어질 때 아래로 내려가는데 2차원 배열에서 아래로 내려가기 위해서는 +1 을 해야 한다는 것입니다.

코드

import Foundation
//MARK: - Properties
let direction = [(-1,0),(1,0),(0,1),(0,-1)]
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let width = input[1] , height = input[0]
var map = Array(repeating: [String](), count: height)
var visited = [[Bool]]()
//좌인지 우인지 파악하기 위한 변수
var i = 0

//MARK: - Input
for y in 0..<height {
    let line = readLine()!.map{String($0)}
    map[y] = line
}

let throwCount = Int(readLine()!)!
let throwHeights = readLine()!.split(separator: " ").map{ height - 1 - (Int(String($0))! - 1)}

// 던진 막대에 특정한 "x"가 맞았다면 제거
func findItemInRow(at height: Int, isleftToRight ltr: Bool? = nil) {
    guard let _ = ltr else {
        for x in stride(from: width - 1, through: 0, by: -1) {
            if map[height][x] == "x" {
                map[height][x] = "."
                return
            }
        }
        return
    }
    for x in 0..<width {
        if map[height][x] == "x" {
            map[height][x] = "."
            return
        }
    }
}

//맵을 벗어났는가?
func isOutOfMap(nx: Int, ny: Int) -> Bool {
    if nx < 0 || nx > width - 1 || ny < 0 || ny > height - 1 {
        return true
    }
    return false
}

// 클러스터 집단이 bottom에 닿아 있는가? = 안전
func isSafetyCluster(y: Int) -> Bool {
    return y == height - 1 ? true : false
}

//만약 isSafety가 false라면 클러스터는 떠있는 상태.
func bfs(x: Int, y: Int) -> (Bool,[(Int,Int)]?) {
    var isSafety = false
    var queue = [(x,y)]
    var index = 0
    while queue.count != index {
        let (curX,curY) = queue[index]
        if !isSafety { isSafety = isSafetyCluster(y: curY) }
        direction.forEach{ dx,dy in
            let (nx,ny) = (curX+dx,curY+dy)
            if isOutOfMap(nx: nx, ny: ny) { return }
            if !visited[ny][nx] && map[ny][nx] == "x" {
                visited[ny][nx] = true
                queue.append((nx,ny))
            }
        }
        index += 1
    }
    return isSafety ? (isSafety,nil) : (isSafety,queue)
}

// 클러스터를 파악하고 떠있는 클러스터를 찾아 unsafetyCluster에 저장
func updateMap() {
    visited = Array(repeating: Array(repeating: false, count: width), count: height)
    var isSafety = true
    var unsafetyCluster = [(Int,Int)]()
    for y in 0..<height {
        for x in 0..<width {
            if map[y][x] == "x" && !visited[y][x] {
                visited[y][x] = true
                let temp = bfs(x: x, y: y)
                if !temp.0 {
                    isSafety = temp.0
                    unsafetyCluster = temp.1!
                }
                
            }
        }
    }
    // 클러스터 집단 떠 있다는 뜻. 내려가야함.
    //일단 맵에 떠있는 클러스터 지우고 -> fixUnsafetyCluster(cluster:)를 통해 내려가도록 고침
    if !isSafety {
        unsafetyCluster.forEach{ (x,y) in
            map[y][x] = "."
        }
        fixUnsafetyCluster(cluster: &unsafetyCluster)
    }
}
// 클러스터가 안전하게 땅이나 다른 집단에 닿을 때 까지 1칸씩 내려감.
func fixUnsafetyCluster(cluster: inout [(Int,Int)]) {
    var isSafety = false
    while !isSafety {
        var visit = Array(repeating: Array(repeating: false, count: width), count: height)
        cluster = cluster.map { (x,y) in
            visit[y+1][x] = true
            return (x,y+1)
        }
       isSafety = checkIsSafedCluster(cluster: cluster, visit: visit)
    }
    cluster.forEach { (x,y) in
        map[y][x] = "x"
    }
}

// 클러스터가 한칸씩 내려가기 위하도록 클러스터 좌표 수정.
func checkIsSafedCluster(cluster: [(Int,Int)], visit: [[Bool]]) -> Bool {
    var index = 0
    while cluster.count != index {
        let (x,y) = cluster[index]
        if y == height - 1 {
            return true
        }
        let (dx,dy) = (0,1)
        let (nx,ny) = (x+dx,y+dy)
        
        if isOutOfMap(nx: nx, ny: ny) { continue }
        if !visit[ny][nx] && map[ny][nx] == "x" { return true }
        index += 1
    }
    return false
}

//MARK: - Main !!
throwHeights.forEach { height in
    findItemInRow(at: height, isleftToRight: i  % 2 == 0 ? true : nil)
    i += 1
    updateMap()
}

for line in map {
    print(line.joined())
}