[백준 2589] 보물섬 (Swift)

문제 : 

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

2589번: 보물섬

 

1. 문제 이해하기

• 행, 열의 크기가 50 이하인 그래프에서 각 칸에 L(육지), W(바다)가 주어지고 육지에서만 상하좌우로 움직일 수 있습니다.
• 한 칸 이동하는데 한 시간이 걸립니다.
• 보물은 여러 개의 육지 덩어리 중에서 육지 칸에서 육지 칸까지 가장 긴 거리 두 곳에 나누어 묻혀있습니다.
• 두 곳 사이의 거리는 최단 시간 경로입니다. 이때의 두 곳 사이의 최단 거리로 이동하는 시간을 출력합니다.

 

2. 문제 풀이 생각하기

1. bfs로 육지일 때만 돌면서 해당 칸에서 다른 칸으로 갈 수 있는 최대 시간을 계속 갱신하는 방식으로 생각했습니다.
2. 중첩 for문으로 L(육지) 일 때만 bfs에 좌표 값을 인자로 넣습니다.
3. bfs에 들어갈 때마다 큐와 visited를 생성(visited는 방문 + dp 역할)
4. while문을 돌면서 큐에 좌표가 있으면 boundary 체크 및 방문 체크를 합니다.
5. 방문을 하지 않은 그래프 위의 좌표라면, 해당 좌표에서 네 방향을 체크합니다.
6. 해당 칸이 L(육지)일 때 방문 체크, 해당 칸까지의 거리와 ans를 비교해서 ans보다 크면 ans 값 갱신, 큐에 [ni, nj] 좌표를 넣습니다.
7. 3 ~ 6 반복
8. ans값 출력

 

3. 차근차근 구현하기

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0], m = input[1]
var g = [[String]]()
let d = [[-1,0], [1,0], [0,-1], [0,1]]
var ans = 0
for _ in 0..<n {
    g.append(readLine()!.map{String($0)})
}

func boundary(_ i: Int, _ j: Int) -> Bool {
    return (0 <= i && i < n) && (0 <= j && j < m)
}
    
func bfs(_ i: Int, _ j: Int) {
    var q = [[i, j]]
    var visited = Array(repeating: Array(repeating: 0, count: m), count: n)
    visited[i][j] = 1
    
    while !q.isEmpty {
        let data = q.removeFirst()
        let i = data[0], j = data[1]
        for k in d {
            let ni = i + k[0], nj = j + k[1]
            if !boundary(ni, nj) || visited[ni][nj] != 0 {
                continue
            }
            if g[ni][nj] == "L" {
                visited[ni][nj] = visited[i][j] + 1
                ans = ans < visited[i][j] ? visited[i][j] : ans
                q.append([ni, nj])
                continue
            }
        }
    }
}
    
for i in 0..<n {
    for j in 0..<m {
        if g[i][j] == "W" {
            continue
        }
        bfs(i, j)
    }
}
print(ans)

 

4. 피드백

• 스위프트 입력받는 것을 제대로 숙지했습니다.