[Algorithm] 백준 - 16946번 벽 부수고 이동하기 4 (Swift)

문제 소개

 

문제 풀이

초기 문제풀이 (시간초과)

처음에는 모든 좌표에서 bfs를 통해 갈수있는 칸수를 계산했지만 역시나 시간초과가 났다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)]

var map = [[Int]]()
var answer = Array(repeating: Array(repeating: 0, count: m), count: n)

for _ in 0..<n {
    let line = Array(readLine()!).map { Int(String($0))! }
    map.append(line)
}

func bfs(_ i: Int, _ j: Int) -> Int {
    var queue: [(i: Int, j: Int)] = [(i, j)]
    var visited = Array(repeating: Array(repeating: false, count: m), count: n)
    var idx = 0
    
    while !queue.isEmpty {
        let poped = queue.removeFirst()
        idx += 1
        
        for d in ds {
            let i = poped.i + d.i
            let j = poped.j + d.j
            
            if 0..<n ~= i && 0..<m ~= j {
                if map[i][j] == 0 && !visited[i][j] {
                    visited[i][j] = true
                    queue.append((i, j))
                }
            }
        }
    }
    
    return idx
}

for i in 0..<n {
    for j in 0..<m {
        if map[i][j] != 0 {
            answer[i][j] = bfs(i, j)
        }
    }
}

for line in answer {
    print(line.map { String($0) }.joined())
}

 

최종 문제풀이 (통과)

group을 만들어서 매번 bfs를 하지 않게 했다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
let diffs: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)]

var map = [[Int]]()

for _ in 0..<n {
    let line = Array(readLine()!).map { Int(String($0))! }
    map.append(line)
}

var group = Array(repeating: Array(repeating: -1, count: m), count: n)
var groupCount = [Int: Int]()
var groupId = 0

func bfs(_ i: Int, _ j: Int) {
    var queue: [(i: Int, j: Int)] = [(i, j)]
    var idx = 0
    
    while !queue.isEmpty {
        let poped = queue.removeFirst()
        idx += 1
                
        for diff in diffs {
            let i = poped.i + diff.i
            let j = poped.j + diff.j
            
            if 0..<n ~= i && 0..<m ~= j {
                if map[i][j] == 0 && group[i][j] == -1 {
                    queue.append((i, j))
                    group[i][j] = groupId
                }
            }
        }
    }
    
    groupCount[groupId] = idx
    groupId += 1
}

for i in 0..<n {
    for j in 0..<m {
        if map[i][j] == 0 && group[i][j] == -1 {
            group[i][j] = groupId
            bfs(i, j)
        }
    }
}

var answer = Array(repeating: Array(repeating: 0, count: m), count: n)

for i in 0..<n {
    for j in 0..<m {
        if map[i][j] == 1 {
            var ids = Set<Int>()
            var count = 0
            
            for diff in diffs {
                let newI = i + diff.i
                let newJ = j + diff.j
                
                if 0..<n ~= newI && 0..<m ~= newJ {
                    ids.insert(group[newI][newJ])
                }
            }
            
            for id in ids {
                count += groupCount[id] ?? 0
            }
            
            answer[i][j] = (count + 1) % 10
        }
    }
}

for line in answer {
    print(line.map { String($0) }.joined())
}