[Swift] 백준 14938번 서강 그라운드

 

서강 그라운드

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

 

 

 

 

풀이

다익스트라

 

1. 1부터 N까지 BFS 반복하면서 최댓값 업데이트

2. 다음 큐의 cost 더했을 때 수색범위 안이고, 다음 큐의 갯수를 더했을 때 현재 아이템 갯수보다 크다면 큐에 추가하기

3. 큐에 들어간 아이템들은 전부 갈 수 있으므로 Set로 관리. bfs 끝난 후 Set에 들어있는 아이템에 해당하는 비용 추가해서 bfs 반환

 

 

소스코드

let NMR = readLine()!.split(separator: " ").map { Int($0)! }
let N = NMR[0], M = NMR[1], R = NMR[2]

var items: [Int] = [0]
items += (readLine()!.split(separator: " ").map { Int($0)! })

var roads: [Int :[(ed: Int, cost: Int)]] = [:]

for _ in 0..<R {
    let tmp = readLine()!.split(separator: " ").map { Int($0)! }
    roads[tmp[0], default: []].append((tmp[1], tmp[2]))
    roads[tmp[1], default: []].append((tmp[0], tmp[2]))
}

func bfs(_ st: Int) -> Int {
    var curItem: [Int] = Array(repeating: 0, count: N+1)
    var que: [(Int, Int)] = [(st, 0)] // 다음 지역, 현재 수색범위
    var vis = Set<Int>()
    vis.insert(st)
    
    var idx = 0
    var res = 0
    while que.count > idx {
        let (q, qLimit) = que[idx]
        
        for (nq, ncost) in roads[q, default: []] {
            if nq == st { continue } // 다음 큐가 시작 지역이라면 넘어가기
            if qLimit + ncost > M { continue } // 다음 큐를 추가했을 때 수색범위 보다 커지면 넘어가기
            
            // 현재 아이템값에 다음 아이템 값을 포함한게, 현재보다 크면
            if items[nq] + curItem[q] > curItem[nq] {
                que.append((nq, ncost + qLimit))
                curItem[nq] = items[nq] + curItem[q]
                vis.insert(nq)
            }
        }
        
        idx += 1
    }
    for vi in vis {
        res += items[vi]
    }
    return res
}


var maxRes = 0

for i in 1...N {
    let res = bfs(i)
    maxRes = max(res, maxRes)
}

print(maxRes)

 

 

반례 모음

반례 1

5 5 4

5 7 8 2 3

1 4 1

5 2 4

3 2 3

1 2 3

정답: 25

 

반례 2

5 5 5

1 2 3 4 5

1 2 2

1 3 4

1 4 2

2 3 4

4 5 2

정답: 15