[2146] 다리 만들기

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

2146번: 다리 만들기

bfs를 두 번 사용해서 풀었다. 중간에 변수명이 겹친걸 못 알아채서 쓸데없는 부분에서 시간을 오래 끌었던 문제였다. 조금 더 집중해서 풀이를 생각하는 연습이 필요한 것 같다.

 

풀이

입력으로 육지와 바다에 대한 구분이 들어온다. 우선 기본적인 bfs를 통해 각 컴포넌트를 구분 짓는 작업을 해준다. 그 이후 한번 더 bfs를 통해 짧은 다리를 찾으면 되는데, 경로탐색의 조건은 다음과 같이 정의했다.

• 상하좌우를 확인하여, 바다인 경우만 큐에 넣고 탐색
• 바다가 아닌 곳이라면 경로탐색 시작 컴포넌트와 다른 컴포넌트인지 확인하여 다른 곳이라면 다리 길이를 갱신 후 종료
• 경로 탐색 중 현재 갱신된 다리 길이보다 길다면 종료

 

정답 코드

주석 처리된 부분은 알맞게 풀고 있는지 확인하려 적은 코드이다.

import Foundation

let n = Int(readLine()!)!
var map = Array(repeating: [Int](), count: n)
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var land = Array(repeating: Array(repeating: 0, count: n), count: n)

for i in 0..<n{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    map[i] = input
}

let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func numbering(x:Int, y:Int, landNumber:Int){
    var q = [[x,y]]
    var dq = [[Int]]()
    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=n || map[nx][ny]==0{ continue }
                if !visited[nx][ny]{
                    visited[nx][ny] = true
                    land[nx][ny] = landNumber
                    q.append([nx,ny])
                }
            }
        }
    }
}

var number = 1
for i in 0..<n{
    for k in 0..<n{
        if !visited[i][k] && map[i][k] != 0{
            visited[i][k] = true
            land[i][k] = number
            numbering(x: i, y: k, landNumber: number)
            number += 1
        }
    }
}
//for l in land{ print(l) }
var ans = n*n
var check = visited
func bridge(ix:Int,ky:Int){
    visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var q = [[ix,ky,0]]
    var dq = [[Int]]()
    let landNumber = land[ix][ky]
    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            let cnt = curr[2]
            if cnt > ans{
                return
            }
            for i in 0..<4{
                let nx = x+dx[i]
                let ny = y+dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=n { continue }
                if !visited[nx][ny] && land[nx][ny]==0{
                    visited[nx][ny] = true
                    q.append([nx,ny,cnt+1])
                }
                if !visited[nx][ny] && land[nx][ny]>0 && land[nx][ny] != landNumber{
//                    print("land[\(ix)][\(ky)]:\(landNumber) -> land[\(nx)][\(ny)]:\(land[nx][ny]), cnt:\(cnt)")
                    ans = min(ans, cnt)
                    return
                }
            }
        }
    }
}

visited = Array(repeating: Array(repeating: false, count: n), count: n)
for x in 0..<n{
    for y in 0..<n{
        if land[x][y]>0{
            bridge(ix: x, ky: y)
        }
    }
}
print(ans)