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

 

2232번: 지뢰

일직선상에 N개의 지뢰가 같은 간격으로 매설되어 있다. 각각의 지뢰는 충격 강도 Pi가 있어서, Pi를 초과하는 힘을 가하면 Pi만큼의 힘을 발휘하며 터지게 된다. 어떤 지뢰가 터지게 되면, 그 지

www.acmicpc.net

너비우선탐색으로 접근한 문제다.

 

풀이

입력받은 지뢰의 충격이 큰 순서부터 터트리면서 너비우선탐색을 수행한다. 이때 터트리는 지뢰의 번호를 입력받은 뒤 오름차순으로 정렬하여 출력하면 된다.

 

정답 코드

import Foundation
let n = Int(readLine()!)!
var visited = Array(repeating: false, count: n)
var arr = [(Int,Int)]()
var map = [Int]()
var ans = [Int]()
func bfs(from a:Int){
ans.append(a+1)
let nx = [-1,1]
var q = [a]
var idx = 0
while idx<q.count{
let curr = q[idx]
let value = map[curr]
for i in 0..<2{
let next = nx[i]+curr
if next<0 || next>=n{ continue }
if !visited[next] && map[next]<value{
visited[next] = true
q.append(next)
}
}
idx += 1
}
}
for i in 0..<n{
let power = Int(readLine()!)!
arr.append((i,power))
map.append(power)
}
arr.sort(by: {$0.1<$1.1})
for _ in 0..<n{
let curr = arr.removeLast()
let idx = curr.0
if !visited[idx]{
visited[idx] = true
bfs(from: idx)
}
}
for ans in ans.sorted(by: <){
print(ans)
}
view raw 2232.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[2350] 대운하  (0) 2022.12.25
[15991] 1, 2, 3 더하기 6  (0) 2022.12.24
[2143] 두 배열의 합  (0) 2022.12.20
[2610] 회의준비  (0) 2022.12.19
[14594] 동방 프로젝트 (Small)  (0) 2022.12.18

+ Recent posts