백준 14890번 경사로 - 스위프트(Swift) 풀이 + 그림 설명

---

 

1. 한 길 내에서 인접한 같은 높이의 칸들을 union 한다. 이때 각 집합의 크기를 기록해둔다.
2. 한 길 내의 모든 칸을 순회하면서 다음 칸으로 갈 수 있는지 체크한다.
    2-1. 다음 칸과의 높이가 1 차이나고, 더 낮은 칸이 속한 집합의 크기가 L 이상이라면 경사로를 놓아서 갈 수 있다.
    2-2. 다음 칸과 높이가 같다면 그냥 갈 수 있다.
    2-3. 그 외의 경우에는 갈 수 없다.

 

1. 한 길 내에서 인접한 같은 높이의 칸들을 union 한다. 이때 각 집합의 크기를 기록해둔다.

 인접한 같은 높이의 칸은 이동할 수 있다. 몇 개가 연속해서 같은 높이인지 쉽게 파악하기 위해 union 하면서 집합의 크기를 기록한다.

 

2. 한 길 내의 모든 칸을 순회하면서 다음 칸으로 갈 수 있는지 체크한다.

 

 2-1. 다음 칸과의 높이가 1 차이나고, 더 낮은 칸이 속한 집합의 크기가 L 이상이라면경사로를 놓아서 갈 수 있다.

 아래와 같은 길을 고려하고 있다고 가정하자. L=2인 경우이다.

 먼저 0번째 칸에서 1번째 칸으로 넘어가야 하는 상황이다. 두 칸의 높이가 1 차이나고, 더 낮은 칸인 2쪽에 L개 이상의 칸이 있기 때문에 경사로를 놓을 수 있다.

 

 이제 경사로를 2쪽에 놓으면 L개 칸이 경사로에 의해 사용되었으므로 2가 속한 집합의 크기를 L만큼 줄여준다.

 

2-2. 다음 칸과 높이가 같다면 그냥 갈 수 있다.

 다음으로 1번째 칸에서 2번째 칸으로 이동하는 경우이다. 두 칸의 높이가 같으므로 그냥 지나갈 수 있다.

 

이어서 계속 진행하는 과정은 아래와 같다.

 

2-3. 그 외의 경우에는 갈 수 없다.

 그 외 두 칸의 높이가 2 이상 차이 나거나, 낮은 칸에 L 이상의 칸이 남아있지 않다면 경사로를 놓을 수 없으므로 지나갈 수 없다.

 

반응형

---

import Foundation

var N = 0, L = 0
var board = Array(repeating: [Int](), count: 100)
var parent = [Int]()
var rank = [Int]()

func find(_ x: Int) -> Int {
    if parent[x] == x { return x }
    
    parent[x] = find(parent[x])
    return parent[x]
}

func union(_ a: Int, _ b: Int) {
    var pa = find(a), pb = find(b)
    
    if pa == pb { return }
    
    if rank[pa] < rank[pb] { swap(&pa, &pb) }
    
    parent[pb] = pa
    rank[pa] += rank[pb]
}

func check(road: [Int]) -> Bool {
    parent = (0..<N).map{ $0 }
    rank = Array(repeating: 1, count: N)
    
    for i in 0..<N-1 {
        if road[i] == road[i+1] {
            union(i, i+1)
        }
    }
    
    for i in 0..<N-1 {
        guard find(i) != find(i+1) else { continue }
        
        guard abs(road[i] - road[i+1]) == 1 else { return false }
        
        if road[i] > road[i+1] {
            if rank[find(i+1)] >= L {
                rank[find(i+1)] -= L
            } else {
                return false
            }
        } else {
            if rank[find(i)] >= L {
                rank[find(i)] -= L
            } else {
                return false
            }
        }
    }
    
    return true
}

func solution() {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    L = input[1]
    
    for i in 0..<N {
        board[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }
    }
    
    var count = 0
    for i in 0..<N {
        let row = board[i]
        let col = (0..<N).map{ board[$0][i] }
        
        let checkRow = check(road: row)
        let checkCol = check(road: col)
        
        if checkRow { count += 1 }
        if checkCol { count += 1 }
    }
    print(count)
}

solution()