[Algorithm/BOJ] 2589 - 보물섬 (BFS) Swift

문제 풀이:

문제에서 시작점이 주어지지 않기 때문에 직접 기준점을 잡아주어야 한다.

 

육지(L)를 기준으로 시작점을 잡는다. 

그 좌표에서 지도를 벗어나지 않고 상화좌우로 이동할 좌표가 육지라는 선에서 이동거리를 1씩 늘려서 갈 수 있는 모든 좌표에 대한 거리를 나타내는 배열에 저장한다.

그리고 시작점에서 갈 수 있는 최대 거리(거리를 나타내는 배열의 최대 값)랑 이 문제의 답이 되는 변수와 비교하여 큰 것을 변수에 저장한다.

모든 육지(L)의 좌표에 대해서 반복한다.

 

코드:

typealias Coord = (r: Int, c: Int)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let m = input[1]
var map = [[String]]()
var result = 0

func soltuion() -> Int {
    for _ in 0..<n {
        let temp = readLine()!
        map.append(Array(temp).map { String($0) })
    }
    
    for r in 0..<n {
        for c in 0..<m {
            if map[r][c] == "L" {
                let temp = bfs(r,c)
                result = max(result, temp)
            }
        }
    }
    
    return result
}

print(soltuion())

func bfs(_ r: Int, _ c: Int) -> Int {
    let d: [Coord] = [(-1,0),(1,0),(0,-1),(0,1)]
    var dist = [[Int]](repeating: [Int](repeating: -1, count: m), count: n)
    dist[r][c] = 0
    var index = 0
    var temp = 0
    
    var q = [Coord]()
    q.append((r, c))
    
    while index<q.count {
        let now = q[index]
        index += 1

        for i in 0..<4 {
            let nr = now.r + d[i].r
            let nc = now.c + d[i].c
            
            if 0<=nr, nr<n, 0<=nc, nc<m {
                if dist[nr][nc] == -1, map[nr][nc] == "L" {
                    q.append((nr, nc))
                    dist[nr][nc] = dist[now.r][now.c]+1
                    temp = max(temp, dist[nr][nc])
                }
            }
        }
    }
    
    return temp
}

 

문제: 

2589번: 보물섬