[Algorithm] 백준 - 2146번 다리 만들기 (Swift)

문제 소개

섬들을 연결하는 최소길이의 다리를 만드는 문제이다.

 

문제 풀이

이 문제에서 풀어야할것은 두가지가 있다. 첫번째는 섬에 번호를 부여하기, 두번째는 최소 다리길이 구하기이다. 둘다 BFS를 활용하여 구했다.

import Foundation

let n = Int(readLine()!)!
var map = [[Int]]()

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

let directions = [(1,0), (0,1), (-1,0), (0,-1)]
var visited = Array(repeating: Array(repeating: false, count: n), count: n)

func makeMap(_ i: Int, _ j: Int) {
    var queue = [(i, j)]
    var idx = 0
    
    while queue.count >= idx + 1 {
        let poped = queue[idx]
        
        for direction in directions {
            let i = poped.0 + direction.0
            let j = poped.1 + direction.1
            
            if i >= 0 && i < n && j >= 0 && j < n && map[i][j] == 1 {
                if !visited[i][j] {
                    visited[i][j] = true
                    map[i][j] = map[poped.0][poped.1]
                    queue.append((i, j))
                }
            }
        }
        
        idx += 1
    }
}

var island = 1

for i in 0..<n {
    for j in 0..<n {
        if !visited[i][j] && map[i][j] == 1 {
            visited[i][j] = true
            map[i][j] = island
            makeMap(i, j)
            island += 1
        }
    }
}

func makeBridge(_ island: Int) -> Int {
    var queue = [(Int, Int)]()
    var distance = Array(repeating: Array(repeating: -1, count: n), count: n)

    for i in 0..<n {
        for j in 0..<n {
            if map[i][j] == island {
                distance[i][j] = 0
                queue.append((i, j))
            }
        }
    }
    
    var idx = 0
    
    while queue.count >= idx + 1 {
        let poped = queue[idx]
        
        for direction in directions {
            let i = poped.0 + direction.0
            let j = poped.1 + direction.1
            
            if i >= 0 && i < n && j >= 0 && j < n {
                if map[i][j] != island && map[i][j] > 0 {
                    return distance[poped.0][poped.1]
                }
                
                if distance[i][j] == -1 && map[i][j] == 0 {
                    distance[i][j] = distance[poped.0][poped.1] + 1
                    queue.append((i, j))
                }
            }
        }
        
        idx += 1
    }
    
    print(distance)

    return 100
}

var answer = 10000

for i in 1..<island {
    answer = min(answer, makeBridge(i))
}

print(answer)