[白俊7576]トマト
1.問題の説明
名トマト
2.問題分析
プローブアルゴリズムを用いてマトリクス図をプローブし,マーキングしながら最大費用を記録した.検索終了後にマトリクスマップに0が残っている場合は、検索できない領域が残っていることを意味します.
プローブアルゴリズムを用いてマトリクス図をプローブし,マーキングしながら最大費用を記録した.検索終了後にマトリクスマップに0が残っている場合は、検索できない領域が残っていることを意味します.
removeAtFirst
では,時間的複雑度O(N)が出現し,タイムアウトが発生する.実際,BFSに比べてキューを実現するために必要な2つの配列の使用方法はより困難である.3.私の回答 import Foundation
struct Queue<T: Equatable> {
var enqueue: [T] = []
var dequeue: [T] = []
init() {}
init(_ queue: [T]) {
enqueue = queue
}
mutating func push(_ element: T) {
enqueue.append(element)
}
mutating func pop() -> T? {
if dequeue.isEmpty {
dequeue = enqueue.reversed()
enqueue.removeAll()
}
return dequeue.popLast()
}
mutating func remove() {
enqueue.removeAll()
dequeue.removeAll()
}
var isEmpty: Bool {
return enqueue.isEmpty && dequeue.isEmpty
}
var firstIndex: T? {
if dequeue.isEmpty {
return enqueue.first
} else {
return dequeue.last
}
}
var lastIndex: T? {
if enqueue.isEmpty {
return dequeue.first
} else {
return enqueue.last
}
}
var count: Int {
return enqueue.count + dequeue.count
}
func contains(_ element: T) -> Bool {
return enqueue.contains(element) || dequeue.contains(element)
}
}
let input = readLine()!.split(separator:" ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])
let dx = [1, -1, 0, 0]
let dy = [0, 0, 1, -1]
var nodes: [[Int]] = Array(repeating: [], count: N)
for i in 0..<N{
let line = readLine()!.split(separator:" ").map{Int(String($0))!}
nodes[i] = line
// 인접 행렬 구현
}
var startNodes:[[Int]] = []
for i in 0..<N{
for j in 0..<M{
if nodes[i][j] == 1{
startNodes.append([i, j, 0])
}
}
}
var answer = BFS(startNodes:startNodes)
for i in 0..<N{
if nodes[i].contains(0){
answer = -1
break
}
}
print(answer)
func BFS(startNodes:[[Int]]) -> Int{
var queue: Queue = Queue(startNodes)
var total = 0
while queue.isEmpty == false{
let input = queue.pop()!
// removeAtFirst를 사용하며 시간 초과 -> 배열 두 개를 통한 큐 구현
let (curRow, curCol, curCnt) = (input[0], input[1], input[2])
total = max(total, curCnt)
for i in 0..<4{
let nextRow = curRow + dy[i]
let nextCol = curCol + dx[i]
if nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M{
continue
}
if nodes[nextRow][nextCol] == 0{
nodes[nextRow][nextCol] = 1
queue.push([nextRow, nextCol, curCnt+1])
}
}
}
return total
}
Reference
この問題について([白俊7576]トマト), 我々は、より多くの情報をここで見つけました
https://velog.io/@j_aion/백준-7576-토마토-25atv693
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import Foundation
struct Queue<T: Equatable> {
var enqueue: [T] = []
var dequeue: [T] = []
init() {}
init(_ queue: [T]) {
enqueue = queue
}
mutating func push(_ element: T) {
enqueue.append(element)
}
mutating func pop() -> T? {
if dequeue.isEmpty {
dequeue = enqueue.reversed()
enqueue.removeAll()
}
return dequeue.popLast()
}
mutating func remove() {
enqueue.removeAll()
dequeue.removeAll()
}
var isEmpty: Bool {
return enqueue.isEmpty && dequeue.isEmpty
}
var firstIndex: T? {
if dequeue.isEmpty {
return enqueue.first
} else {
return dequeue.last
}
}
var lastIndex: T? {
if enqueue.isEmpty {
return dequeue.first
} else {
return enqueue.last
}
}
var count: Int {
return enqueue.count + dequeue.count
}
func contains(_ element: T) -> Bool {
return enqueue.contains(element) || dequeue.contains(element)
}
}
let input = readLine()!.split(separator:" ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])
let dx = [1, -1, 0, 0]
let dy = [0, 0, 1, -1]
var nodes: [[Int]] = Array(repeating: [], count: N)
for i in 0..<N{
let line = readLine()!.split(separator:" ").map{Int(String($0))!}
nodes[i] = line
// 인접 행렬 구현
}
var startNodes:[[Int]] = []
for i in 0..<N{
for j in 0..<M{
if nodes[i][j] == 1{
startNodes.append([i, j, 0])
}
}
}
var answer = BFS(startNodes:startNodes)
for i in 0..<N{
if nodes[i].contains(0){
answer = -1
break
}
}
print(answer)
func BFS(startNodes:[[Int]]) -> Int{
var queue: Queue = Queue(startNodes)
var total = 0
while queue.isEmpty == false{
let input = queue.pop()!
// removeAtFirst를 사용하며 시간 초과 -> 배열 두 개를 통한 큐 구현
let (curRow, curCol, curCnt) = (input[0], input[1], input[2])
total = max(total, curCnt)
for i in 0..<4{
let nextRow = curRow + dy[i]
let nextCol = curCol + dx[i]
if nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M{
continue
}
if nodes[nextRow][nextCol] == 0{
nodes[nextRow][nextCol] = 1
queue.push([nextRow, nextCol, curCnt+1])
}
}
}
return total
}
Reference
この問題について([白俊7576]トマト), 我々は、より多くの情報をここで見つけました https://velog.io/@j_aion/백준-7576-토마토-25atv693テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol