[코딩테스트] 🗺️ 보물섬 - 백준 2589

유형

BFS

소요시간

40분

회고

어제 풀었던 BFS 문제에서 백트래킹이 빠진 유형이어서 할만 했다. index 범위 처리, 거리 계산 등

그러나 숙달되지는 않은 것 같다.

코드

let nm = readLine()!.split(separator: " ").map { Int($0)! }
    let (n, m) = (nm[0], nm[1])

    var land = [(Int, Int)]()
    var board: [[Character]] = Array(repeating: Array(repeating: "W", count: m), count: n)

    let landCount = land.count

    (0..<n).forEach { i in
        readLine()!.enumerated().forEach { j, c in
            board[i][j] = c
            if c == "L" { land.append((i, j))}
        }
    }

    let dr = [-1, 1, 0, 0]
    let dc = [0, 0, 1, -1]
    var answer = 0

    func bfs(start: (Int, Int)) -> Int {
        var dist = Array(repeating: Array(repeating: -1, count: m), count: n)

        var queue: [(Int, Int)] = [start]
        dist[start.0][start.1] = 0
        var head = 0

        var local = 0

        while head < queue.count {
            let start = queue[head]
            head += 1
            local = max(local, dist[start.0][start.1])

            (0..<4).forEach { d in
                let nr = start.0 + dr[d]
                let nc = start.1 + dc[d]
                if nr < 0 || nr >= n || nc < 0 || nc >= m { return }
                if board[nr][nc] == "W" { return }
                if dist[nr][nc] != -1 { return }

                dist[nr][nc] = dist[start.0][start.1] + 1
                queue.append((nr, nc))
            }
        }

        return local
    }

    land.forEach { i in
        let dist = bfs(start: i)
        answer = max(answer, dist)
    }

    print(answer)