[Swift 알고리즘] 백준 BOJ - 2146 다리 만들기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 2146 다리 만들기" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

2146번: 다리 만들기

 

---

풀이

이번 문제는 bfs 문제입니다.

이번 문제에서 요구하는 것은 다리의 최소 길이이므로 bfs를 사용해야 합니다.

 

bfs와 dfs 둘 다 사용할 수 있는 부분도 있는데요. 바로 섬의 라벨링입니다.

섬을 라벨링 하지 않는다면 bfs를 이용해 다리의 길이를 구할 때 다른 섬과 연결된 것인지, 같은 섬과 연결된 것인지 알 방법이 없습니다.

따라서 섬에 각자 다른 숫자로 라벨링을 해줘야 합니다.

 

저는 bfs를 이용해 라벨링을 진행했는데요. dfs를 사용해도 상관 없습니다.

숫자 하나를 정해서(저는 10으로 진행) bfs를 이용해 연결된 땅에 같은 숫자로 채워줍니다.

 

라벨링이 끝났다면 다리의 길이를 구하는 bfs를 진행해야 합니다.

map[x][y]에서 시작해서 상하좌우를 살피며 자신과 다른 섬 혹은 바다를 탐색합니다.

만약 바다라면 queue에 넣고 다른 섬이라면 현재의 result와 연결된 다리 길이 중 최소를 구합니다.

 

마지막에 구해진 최소 다리 길이를 출력하면 됩니다.

 

---

전체 코드

//2146 다리 만들기
import Foundation

let input = Int(readLine()!)!
var result = -1

var map: [[Int]] = []
for _ in 0..<input {
    let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
    map.append(input)
}

let dx: [Int] = [1, -1, 0, 0]
let dy: [Int] = [0, 0, -1, 1]
func bfs1(x: Int, y: Int, label: Int) {
    var queue: [(x: Int, y: Int)] = [(x, y)]
    var index = 0
    
    map[x][y] = label
    
    while index < queue.count {
        let first = queue[index]
        index += 1
        
        for i in 0..<4 {
            let nx = first.x + dx[i]
            let ny = first.y + dy[i]
            
            if nx >= 0 && nx < input && ny >= 0 && ny < input {
                if map[nx][ny] == 1 {
                    map[nx][ny] = label
                    queue.append((nx, ny))
                }
            }
        }
    }
}

func bfs2(x: Int, y: Int) {
    var queue: [(x: Int, y: Int, count: Int)] = [(x, y, 0)]
    var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: input), count: input)
    var index = 0

    visited[x][y] = true
    
    while index < queue.count {
        let first = queue[index]
        index += 1
        
        for i in 0..<4 {
            let nx = first.x + dx[i]
            let ny = first.y + dy[i]
            let nCount = first.count + 1
            
            if nx >= 0 && nx < input && ny >= 0 && ny < input {
                if map[nx][ny] != map[x][y] && !visited[nx][ny] {
                    if map[nx][ny] != 0 {
                        index = queue.count
                        result = result < 0 ? nCount : min(result, first.count)
                        break
                    }
                    
                    visited[nx][ny] = true
                    queue.append((nx, ny, nCount))
                }
            }
        }
    }
}

var label: Int = 10
for i in 0..<input {
    for j in 0..<input {
        if map[i][j] == 1 {
            bfs1(x: i, y: j, label: label)
            label += 1
        }
    }
}

for i in 0..<input {
    for j in 0..<input {
        if map[i][j] != 0 {
            bfs2(x: i, y: j)
        }
    }
}

print(result)

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.