안녕하세요. 개발 중인 정주입니다.
오늘은 "백준 BOJ - 2146 다리 만들기" 문제를 풀었습니다.
Github
GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘
스위프트 알고리즘. Contribute to jeongju9216/SwiftAlgorithm development by creating an account on GitHub.
github.com
문제 링크
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
풀이
이번 문제는 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)
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.