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

2024. 5. 20. 17:46· → Problems
목차
  1. 문제 소개
  2. 문제 풀이

문제 소개

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

 

문제 풀이

이 문제에서 풀어야할것은 두가지가 있다. 첫번째는 섬에 번호를 부여하기, 두번째는 최소 다리길이 구하기이다. 둘다 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)

'→ Problems' 카테고리의 다른 글

[Algorithm] 백준 - 14226번 이모티콘 (Swift)  (0) 2024.05.22
[Algorithm] 백준 - 13913번 숨바꼭질4 (Swift)  (0) 2024.05.21
[Algorithm] 백준 - 16964번 DFS 스페셜 저지 (Swift)  (0) 2024.05.14
[Algorithm] 백준 - 16940번 BFS 스페셜 저지 (Swift)  (0) 2024.05.14
[Algorithm] 백준 - 7576번 토마토 (Swift)  (0) 2024.05.13
  1. 문제 소개
  2. 문제 풀이
'→ Problems' 카테고리의 다른 글
  • [Algorithm] 백준 - 14226번 이모티콘 (Swift)
  • [Algorithm] 백준 - 13913번 숨바꼭질4 (Swift)
  • [Algorithm] 백준 - 16964번 DFS 스페셜 저지 (Swift)
  • [Algorithm] 백준 - 16940번 BFS 스페셜 저지 (Swift)
Swift librarian
Swift librarian
Swift librarian
Swift Library
Swift librarian
전체
오늘
어제
  • 분류 전체보기 (231)
    • 📺 Programming (5)
    • → Architecture (2)
    • → Design Pattern (0)
    • → Computer Science (15)
    • ⚙️ Algorithm (0)
    • → 알고리즘 관련 (22)
    • → Problems (104)
    • 🚀 Project (0)
    • → 알쏭달쏭 (0)
    • → Shook (2)
    • → Solver (8)
    • → Taster (7)
    • → Outline (4)
    • → Pointer (2)
    • → Guesser (3)
    • 🦜 Swift (2)
    • → Swift Archive (12)
    • → Swift Study (12)
    • → Xcode (6)
    • 🧰 Framework (0)
    • → Foundation (1)
    • → UIKit (2)
    • → SwiftUI (3)
    • → CoreData (2)
    • → MapKit (1)
    • → CoreHaptic (1)
    • → User Notification (1)
    • → StoreKit (2)
    • 🏛️ Library (0)
    • → TCA (0)
    • 🐈‍⬛ Git (8)
    • → Git의 원리 (2)
    • → Git 심화 (1)
    • 📦 Other (1)
    • 👦🏻 Log (0)

최근 글

hELLO · Designed By 정상우.v4.2.2
Swift librarian
[Algorithm] 백준 - 2146번 다리 만들기 (Swift)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.