문제 링크 (opens new window)

초기 풀이(오답 - 시간초과)

1. DFS로 섬끼리 분리
2. 섬을 딕셔너리로 위치좌표 분리
3. 섬 내부끼리 nC2 조합으로 좌표별 최단거리 구하기
4. 최단거리 중 최댓값 구하기

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head: Int = 0

    var count: Int {
        return array.count - head
    }

    var isEmpty: Bool {
        return count == 0
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

// 1 1 1
// 1 1 1
// 1 1 1
// 1^2 2^2 3^2
// sigma(k^2)

let dy = [-1, 0, 1, 0]; let dx = [0, 1 , 0, -1]
let mn = readLine()!.split(separator: " ").map { Int($0)! }; let m = mn[0]; let n = mn[1]
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: n), count: m)
var shortcut: [[Int]] = .init(repeating: .init(repeating: 0, count: n), count: m)
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: n), count: m)
var adjList: [[Int]] = .init(repeating: [], count: m)
var ret = 0
var groups: [Int: [(Int, Int)]] = [:] // 육지 좌표 모음집
// dfs로 육지 그룹화
// 육지 내에서 2개 조합
// 모든 2개 최단거리 계산
func dfs(_ y: Int, _ x: Int, _ ret: Int) {
    visited[y][x] = true
    if let _ = groups[ret] {
        groups[ret]!.append((y, x))
    } else {
        groups[ret] = [(y, x)]
    }

    for i in 0..<4 {
        let ny = dy[i] + y
        let nx = dx[i] + x

        if ny < 0 || nx < 0 || ny >= m || nx >= n || visited[ny][nx] || adj[ny][nx] == 0 {
            continue
        }

        dfs(ny, nx, ret)
    }
}

func combination<T>(_ elements: [T], _ k: Int) -> [[T]] {
    var results: [[T]] = []

    func combi(_ index: Int, _ now: [T]) {
        if now.count == k {
            results.append(now)
            return
        }

        for i in index..<elements.count {
            combi(i + 1, now + [elements[i]])
        }
    }
    combi(0, [])
    return results
}

func bfs(_ here: (Int, Int)) {
    shortcut = .init(repeating: .init(repeating: 0, count: n), count: m)
    var q = Queue<(Int, Int)>()
    shortcut[here.0][here.1] = 1
    q.enqueue(here)

    while(!q.isEmpty) {
        guard let here = q.dequeue() else { return }

        for i in 0..<4 {
            let ny = dy[i] + here.0
            let nx = dx[i] + here.1

            if ny < 0 || nx < 0 || ny >= m || nx >= n || shortcut[ny][nx] != 0 || adj[ny][nx] == 0 {
                continue
            }

            shortcut[ny][nx] = shortcut[here.0][here.1] + 1
            q.enqueue((ny, nx))
        }
    }
}

for i in 0..<m {
    let row: String = readLine()!
    for (index, char) in row.enumerated() {
        if char == "L" {
            adj[i][index] = 1
        } else if char == "W" {
            adj[i][index] = 0
        }
    }
}

for i in 0..<m {
    for j in 0..<n {
        if visited[i][j] || adj[i][j] == 0 {
            continue
        }
        dfs(i, j, ret)
        ret += 1
    }
}

// 육지 내에서는 가장 긴 거리
var result = Int.min
for (_, value) in groups {
    var longWay = Int.min
    for selected in combination(value, 2) {
        bfs(selected[0])
        longWay = max(longWay, shortcut[selected[1].0][selected[1].1])
    }
    result = max(longWay, result)
}

print(result - 1)

수정 풀이

1. 모든 좌표에 대해 BFS를 돌리면서 실시간으로 최댓값을 계산하여 마지막에 한번만 리턴

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head: Int = 0

    var count: Int {
        return array.count - head
    }

    var isEmpty: Bool {
        return count == 0
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let dy = [-1, 0, 1, 0]; let dx = [0, 1 , 0, -1]
let mn = readLine()!.split(separator: " ").map { Int($0)! }; let m = mn[0]; let n = mn[1]
var visited: [[Int]] = .init(repeating: .init(repeating: 0, count: n), count: m)
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: n), count: m)
var result = Int.min
var groups: [Int: [(Int, Int)]] = [:] // 육지 좌표 모음집

func bfs(_ here: (Int, Int)) {
    visited = .init(repeating: .init(repeating: 0, count: n), count: m)
    var q = Queue<(Int, Int)>()
    visited[here.0][here.1] = 1
    q.enqueue(here)

    while(!q.isEmpty) {
        guard let here = q.dequeue() else { return }

        for i in 0..<4 {
            let ny = dy[i] + here.0
            let nx = dx[i] + here.1

            if ny < 0 || nx < 0 || ny >= m || nx >= n || visited[ny][nx] != 0 || adj[ny][nx] == 0 {
                continue
            }

            visited[ny][nx] = visited[here.0][here.1] + 1
            q.enqueue((ny, nx))
            result = max(visited[ny][nx], result)
        }
    }
}

for i in 0..<m {
    let row: String = readLine()!
    for (index, char) in row.enumerated() {
        if char == "L" {
            adj[i][index] = 1
        } else if char == "W" {
            adj[i][index] = 0
        }
    }
}

// 육지 내에서는 가장 긴 거리
// BFS 위치별로 돌리고, max(visited) 최댓값 계산
for i in 0..<m {
    for j in 0..<n {
        if (adj[i][j] == 1) {
            bfs((i, j))
        }
    }
}
print(result - 1)