[Swift] 백준_다리 만들기(2146)

문제

 

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

 

풀이

 

간단히 말하면, 각 섬에서 바다와 만나는 칸에서 다른 섬들과의 최단거리를 찾아서 해결했다.

 

 

우선, 다른 영역을 구하는 문제들과 동일하게 모든 점을 확인하기 위해 중첩된 반복문을 이용하였다. 1인 점을 만났을때, 방문한 기록이 없다면 bfs를 이용해 섬을 찾아준다.

 

섬을 찾고나면 map이라는 변수는 섬 부분만 0이고 나머지는 -1로 초기화가 되어있을 것이다. 이때, 바다와 인접한 칸(0과 인접한 1의 좌표)은 tempIsland라는 변수에 따로 저장해두었다.

 

첫 번째 while문이 종료되면 위에서 말했듯이 map이 초기화되어있고, tempIsland에는 바다와 인접한 칸의 좌표가 있을 것이다. 이제 tempIsland의 원소마다 각각 다른 섬들과의 최단 거리를 확인해야한다.

이번에도 BFS를 이용하는데, 이번에는 영역이 아닌 최단거리 문제들과 동일하게 거리를 구해주면된다. while문을 진행하다 1을 만났을 때, result의 값과 비교해서 더 작은 값을 result에 넣어주면된다. BFS의 특성상 가장 먼저 나온 값이 최단거리이므로 바로 continue를 이용해 다음 tempIsland원소로 넘어가면된다. 

 

이렇게하면 하나의 섬에 대한 코드가 끝난다. 이제 다시 위로 올라가 다음 섬을 찾아서 반복해주면된다.

이때,

import Foundation

let n = Int(readLine()!)!
var country: [[Int]] = []
for _ in 0..<n {
    country.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var result = 9999999
var queue: [[Int]] = []
var map = Array(repeating: Array(repeating: -1, count: n), count: n)
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
for i in 0..<n {
    for j in 0..<n {
        if country[i][j] == 1 && !visited[i][j] {
            map = Array(repeating: Array(repeating: -1, count: n), count: n)
            map[i][j] = 0
            visited[i][j] = true
            queue = [[i,j]]
            var tempIsland: [[Int]] = []
            while !queue.isEmpty {
                let current = queue.removeFirst()
                for k in 0..<dx.count {
                    let newX = current[0] + dx[k]
                    let newY = current[1] + dy[k]
                    if newX < 0 || newY < 0 || newX >= n || newY >= n {
                        continue
                    }
                    if country[newX][newY] == 0 && !visited[newX][newY] {
                        tempIsland.append([current[0],current[1]])
                        continue
                    }
                    if !visited[newX][newY] && country[newX][newY] == 1 {
                        visited[newX][newY] = true
                        map[newX][newY] = 0
                        queue.append([newX,newY])
                    }
                }
            }
            tempIsland = Array(Set(tempIsland))
        secondOuter: for start in tempIsland {
            queue = [start]
            var tempMap = map
            while !queue.isEmpty {
                let current = queue.removeFirst()
                for k in 0..<dx.count {
                    let newX = current[0] + dx[k]
                    let newY = current[1] + dy[k]
                    if newX < 0 || newY < 0 || newX >= n || newY >= n {
                        continue
                    }
                    if tempMap[newX][newY] == -1 && country[newX][newY] == 0 {
                        queue.append([newX,newY])
                        tempMap[newX][newY] = tempMap[current[0]][current[1]] + 1
                        continue
                    }
                    if tempMap[newX][newY] == -1 && country[newX][newY] == 1 {
                        result = min(result,tempMap[current[0]][current[1]])
                        continue secondOuter
                    }
                }
            }
        }
        }
    }
}
print(result)

각 섬이 서로 다른 map을 이용해야하므로 tempMap을 사용했따. 또한, map이 달라지면 이전 섬을 방문했는지 알 수 없기 때문에 visited변수도 같이 사용해주었다.

 

 

_____________________________________________________________________________________________________

 

 

처음 풀이를 생각했을 때 시간초과가 날 줄 알았는데 구현해보길 잘한듯. 일단 해보기