https://www.acmicpc.net/problem/2232
너비우선탐색으로 접근한 문제다.
풀이
입력받은 지뢰의 충격이 큰 순서부터 터트리면서 너비우선탐색을 수행한다. 이때 터트리는 지뢰의 번호를 입력받은 뒤 오름차순으로 정렬하여 출력하면 된다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} |
'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 |