[백준 2933] 미네랄 (Swift)

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

 

Simulation & BFS

R*C 칸의 격자판이 있고, 양쪽에서 번갈아가면서 h 높이의 미네랄들을 한개씩 없앤다.

미네랄들은 바닥부터 연결되어 있어야 유지될 수 있는데, 지지층 없이 떠있는 미네랄들은 그대로 떨어진다.

떨어지는 미네랄들은 모양이 일정하게 유지된다. 다 치고난 후에 동굴의 미네랄 모양을 출력하는 문제

 

 

접근방법

오늘도 테트리스같은 문제다..

BFS를 써서 떠있는 미네랄들을 배열에 담고 그 미네랄들을 모양을 유지하면서 그대로 얼만큼 내려야 하는지 알아봐야한다.

으~

 

오답노트

맨처음엔 왼쪽오른쪽 반대로 해서 틀렸었고,

마지막에는 이 아래 코드 부분 범위 때문에 골치아팠다.

while m.0 + tmp < R {
    if map[m.0+tmp][m.1] == "x" {
        break
    }
    tmp += 1
}
if m.0+tmp == R || !visit[m.0+tmp][m.1] { // 같은 클러스터인 경우 count하지 않음
    len = min(len, tmp)
}

 

떠있는 클러스터에서 아래로 얼만큼의 빈공간이 있는지 계산하는 구간인데,

바닥까지 빈공간일 때 클러스터 행 위치 + tmp는 R을 가리키기 때문에 visit[][] 범위를 초과한다. 그치만 이때도 tmp로 len 갱신은 해주어야 하고,

R보다 작더라도 visit가 true면 (즉, 같이 붕 떠있는 클러스터 칸 중 하나면) 그 tmp로 len을 갱신하면 안된다.

OR 연산자를 쓰면 앞쪽이 true면 뒤쪽 계산을 안하니까 이렇게 써줘도 out of range 에러는 피해갈 수 있었다.

 

소스코드

import Foundation

func solution() {
    let RC:[Int] = readLine()?.split(separator: " ").map { Int($0) } as! [Int]
    let (R, C):(Int, Int) = (RC[0], RC[1])
    
    var map:[[Character]] = []
    
    for _ in 0..<R {
        map.append(Array(readLine()!))
    }
    
    let _:Int = Int(readLine()!)!
    let heights:[Int] = readLine()?.split(separator: " ").map { Int($0) } as! [Int]
    
    let dr = [0,0,1,-1]
    let dc = [-1,1,0,0]

    for (i,height) in heights.enumerated() {
        // 막대 던지기
        let realH = R-height
        let left2Right = (i % 2 == 0) // 짝면 왼->오
        let seq = left2Right ? Array(0..<C) : Array(0..<C).reversed()
        // 미네랄 파괴
        for c in seq {
            if map[realH][c] == "x" {
                map[realH][c] = "."
                break
            }
        }
        // 클러스터 하강
        // 떠있는 클러스터 모으기 bfs
        var q:[(Int,Int)] = []
        var visit:[[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: C), count: R)
        // 바닥에 있는 미네랄 모두 넣어줌
        for c in 0..<C {
            if map[R-1][c] == "x" {
                visit[R-1][c] = true
                q.append((R-1,c))
            }
        }
        //bfs
        while !q.isEmpty {
            let here:(Int,Int) = q.popLast()!
            for i in 0..<4 {
                let (nr,nc) = (here.0 + dr[i], here.1 + dc[i])
                if nr >= 0, nr < R, nc >= 0, nc < C, map[nr][nc] == "x", !visit[nr][nc] {
                    visit[nr][nc] = true
                    q.append((nr,nc))
                }
            }
        }
        
        var floatingM:[(Int,Int)] = []
        for r in 0..<R {
            for c in 0..<C {
                if !visit[r][c], map[r][c] == "x" {
                    floatingM.append((r,c))
                }
            }
        }
        
        visit = [[Bool]](repeating: [Bool](repeating: false, count: C), count: R)
        for m in floatingM {
            visit[m.0][m.1] = true
        }
        
        floatingM.sort { a, b in
            if a.0 == b.0 {
                return a.1 < b.1
            } else {
                return a.0 < b.0
            }
        }
        
        // 내려갈 거리
        var len = 100
        for m in floatingM {
            if map[m.0 + 1][m.1] == "." {
                var tmp = 1
                while m.0 + tmp < R {
                    if map[m.0+tmp][m.1] == "x" {
                        break
                    }
                    tmp += 1
                }
                if m.0+tmp == R || !visit[m.0+tmp][m.1] { // 같은 클러스터인 경우 count하지 않음
                    len = min(len, tmp)
                }
            }
        }
        len -= 1
        
        // swap
        while !floatingM.isEmpty {
            let now:(Int,Int) = floatingM.popLast()!
            let tmp = map[now.0+len][now.1]
            map[now.0+len][now.1] = map[now.0][now.1]
            map[now.0][now.1] = tmp
        }
    }
    
    map.forEach { row in
        print(String(row))
    }
}

solution()

 

떠있는 클러스터 탐색, 클러스터 하강 부분 참고한 블로그: https://charles098.tistory.com/137