백준 16946번 벽 부수고 이동하기 4 - 스위프트(Swift) 풀이 + 그림 설명

---

 

1. DFS를 돌면서 인접한 빈칸들을 union 한다.
2. union 할 때 각 집합의 크기를 기록해둔다.
3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다.

 

1. DFS를 돌면서 인접한 빈칸들을 union 한다.

 빈칸들이 인접해있으면 인접한 빈칸을 모두 방문할 수 있다. 따라서 인접한 빈칸들을 유니온 파인드를 사용해 하나의 집합으로 처리해준다.

 

2. union 할 때 각 집합의 크기를 기록해둔다.

 방문할 수 있는 빈칸의 개수를 알아야 하기 때문에 각 집합의 크기를 구해둬야 한다. 두 집합을 union 할 때 크기도 같이 합쳐서 기록해두자.

 

3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다.

 어떤 벽을 부수면, 벽 때문에 막혀있던 상하좌우 칸들이 연결되게 된다. 따라서 어떤 벽을 부쉈을 때 방문할 수 있는 칸의 수는 (상하좌우의 집합들의 크기의 합) + 1 이 된다.

 

 이때 상하좌우의 집합 중 중복이 발생할 수 있다는 점을 주의해야 한다. 아래와 같은 상황에서 오른쪽 집합과 아래쪽 집합이 같은 집합이므로 중복으로 처리하여 집합의 크기를 한 번만 더해주어야 한다.

반응형

---

import Foundation

var N = 0, M = 0
var map = Array(repeating: [Int](), count: 1001)
var result = Array(repeating: Array(repeating: 0, count: 1001), count: 1001)
var parent = Array(repeating: Array(repeating: Pair(0,0), count: 1001), count: 1001)
var rank = Array(repeating: Array(repeating: 1, count: 1001), count: 1001)
var visit = Array(repeating: Array(repeating: false, count: 1001), count: 1001)

struct Pair: Hashable {
    let row: Int
    let col: Int
    
    init(_ row: Int, _ col: Int) {
        self.row = row
        self.col = col
    }
    
    var adjacents: [Pair] {
        return [Pair(row+1,col), Pair(row-1,col), Pair(row,col+1), Pair(row,col-1)]
                .filter { (0..<N) ~= $0.row && (0..<M) ~= $0.col }
    }
}

func find(_ p: Pair) -> Pair {
    if parent[p.row][p.col] == p { return p }
    
    parent[p.row][p.col] = find(parent[p.row][p.col])
    
    return parent[p.row][p.col]
}

func union(_ p1: Pair, _ p2: Pair) {
    var parentP1 = find(p1), parentP2 = find(p2)
    
    if parentP1 == parentP2 { return }
    
    if rank[parentP1.row][parentP1.col] < rank[parentP2.row][parentP2.col] {
      swap(&parentP1, &parentP2)
    }
    
    parent[parentP2.row][parentP2.col] = parentP1
    rank[parentP1.row][parentP1.col] += rank[parentP2.row][parentP2.col]
}

func DFS(_ p: Pair) {
    visit[p.row][p.col] = true
    
    for adj in p.adjacents {
        guard !visit[adj.row][adj.col] && map[adj.row][adj.col] == 0 else { continue }
        
        union(p, adj)
        DFS(adj)
    }
}

func initParent() {
    for i in 0..<N {
        for j in 0..<M {
            parent[i][j] = Pair(i, j)
        }
    }
}

func unionPairs() {
    initParent()
    
    for i in 0..<N {
        for j in 0..<M {
            guard !visit[i][j] && map[i][j] == 0 else { continue }
            DFS(Pair(i, j))
        }
    }
}

func breakTheWall() {
    for i in 0..<N {
        for j in 0..<M {
            guard map[i][j] != 0 else { continue }
            
            var count = 1
            
            let adjacentSet = Set(Pair(i, j).adjacents.map{ find($0) })
            for adjSet in adjacentSet {
                guard map[adjSet.row][adjSet.col] == 0 else { continue }
                
                count += rank[adjSet.row][adjSet.col]
            }
            
            result[i][j] = count % 10
        }
    }
}

func solution() {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    for i in 0..<N { map[i] = readLine()!.map{ Int(String($0))! } }
    
    unionPairs()
    breakTheWall()
    
    var resultString = ""
    
    for i in 0..<N {
        for j in 0..<M {
            resultString.write("\(result[i][j])")
        }
        resultString.write("\n")
    }
    
    print(resultString)
}

solution()