알고리즘 문제
백준 4179 - 불!(Swift)
레옹아범
2023. 12. 12. 15:54
반응형
백준 4179 - 불!(Swift)
접근법
- 지훈이를 우선적으로 BFS를 실행하며 한번 실행할 때마다 현재 큐에 있는 불 개수만큼 불을 추가함
- 이후 현재 지훈이의 위치 중 x, y가 하나라도 경계에 들어올 경우 종료
실패코드(메모리 초과)
import Foundation
struct Queue<T> {
private var enqueueStack: [T] = []
private var dequeueStack: [T] = []
var isEmpty: Bool {
return enqueueStack.isEmpty && dequeueStack.isEmpty
}
var count: Int {
return enqueueStack.count + dequeueStack.count
}
mutating func enqueue(_ value: T) {
enqueueStack.append(value)
}
mutating func dequeue() -> T? {
if dequeueStack.isEmpty {
dequeueStack = enqueueStack.reversed()
enqueueStack.removeAll()
}
return dequeueStack.popLast()
}
}
func bfs(graph: [[Int]], jihoonCoordinate: (x: Int, y: Int), fireQueue: Queue<(x: Int, y: Int)>) -> Int {
let dxs = [0, 0, -1, 1]
let dys = [-1, 1, 0, 0]
var jihoonQueue = Queue<(x: Int, y: Int)>()
var fireQueue = fireQueue
var answer = Array(repeating: Array(repeating: 0, count: graph[0].count), count: graph.count)
var jihoonValue = Array(repeating: Array(repeating: 0, count: graph[0].count), count: graph.count)
jihoonQueue.enqueue(jihoonCoordinate)
answer[jihoonCoordinate.x][jihoonCoordinate.y] = 1
jihoonValue[jihoonCoordinate.x][jihoonCoordinate.y] = 1
while !jihoonQueue.isEmpty {
let coordinate = jihoonQueue.dequeue()!
if answer[coordinate.x][coordinate.y] < 0 { continue }
if coordinate.x == 0 || coordinate.x == (graph.count - 1) || coordinate.y == 0 || coordinate.y == (graph[0].count - 1) { return answer[coordinate.x][coordinate.y] }
for (dx, dy) in zip(dxs, dys) {
let x = coordinate.x + dx
let y = coordinate.y + dy
if x < 0 || x >= graph.count || y < 0 || y >= graph[0].count || graph[x][y] != 0 || answer[x][y] != 0 {
continue
}
jihoonQueue.enqueue((x, y))
answer[x][y] = jihoonValue[coordinate.x][coordinate.y] + 1
jihoonValue[x][y] = answer[x][y]
}
for _ in 0..<fireQueue.count {
let fireCoordinate = fireQueue.dequeue()!
for (dx, dy) in zip(dxs, dys) {
let fireX = fireCoordinate.x + dx
let fireY = fireCoordinate.y + dy
if fireX < 0 || fireX >= graph.count || fireY < 0 || fireY >= graph[0].count || graph[fireX][fireY] == Int.max {
continue
}
fireQueue.enqueue((fireX, fireY))
answer[fireX][fireY] = -1
}
}
}
return 0
}
func solution4179() {
let miroInfos = readLine()!.split(separator: " ").map { Int($0)! }
let (R, C) = (miroInfos[0], miroInfos[1])
var graph: [[Int]] = []
var jihoonCoordinate = (x: 0, y: 0)
var fireQueue = Queue<(x: Int, y: Int)>()
for x in 0..<R {
let arr: [Int] = Array(readLine()!).map { val in
switch val {
case "J":
return 1
case "F":
return -1
case "#":
return Int.max
default:
return 0
}
}
if arr.contains(1) {
let y = arr.firstIndex(of: 1)!
jihoonCoordinate = (x, y)
}
graph.append(arr)
}
for x in 0..<R {
for y in 0..<C {
if graph[x][y] == -1 {
fireQueue.enqueue((x, y))
}
}
}
let answer = bfs(graph: graph, jihoonCoordinate: jihoonCoordinate, fireQueue: fireQueue)
if answer == 0 {
print("IMPOSSIBLE")
} else {
print(answer)
}
}
solution4179()- 대부분의 반례에도 통과하고 문제는 맞지만 메모리 문제가 터진다
- 그 이유는 불이 퍼지는 과정이 매번 반복되기 때문인데, 지훈이가 현재 위치에서 4번 이동할 경우 불이 4초 뒤까지 퍼지게끔 구현을 하여 메모리 문제가 아니더라도 실패한 코드다.
- 또한, 하나의 노드를 방문할 때마다 최대 16번의 불이 번지는 작업이 발생하기 때문에 시간 관련 문제도 생길 것 같다.
성공코드
mport Foundation
struct Queue<T> {
private var enqueueStack: [T] = []
private var dequeueStack: [T] = []
var isEmpty: Bool {
return enqueueStack.isEmpty && dequeueStack.isEmpty
}
var count: Int {
return enqueueStack.count + dequeueStack.count
}
mutating func enqueue(_ value: T) {
enqueueStack.append(value)
}
mutating func dequeue() -> T? {
if dequeueStack.isEmpty {
dequeueStack = enqueueStack.reversed()
enqueueStack.removeAll()
}
return dequeueStack.popLast()
}
}
func bfsFire(graph: [[Int]]) -> [[Int]] {
let dxs = [0, 0, -1, 1]
let dys = [-1, 1, 0, 0]
var queue = Queue<(x: Int, y: Int)>()
var answer = Array(repeating: Array(repeating: 0, count: graph[0].count), count: graph.count)
var isVisited = Array(repeating: Array(repeating: false, count: graph[0].count), count: graph.count)
for x in 0..<graph.count {
for y in 0..<graph[0].count {
if graph[x][y] == -1 {
queue.enqueue((x, y))
answer[x][y] = -1
isVisited[x][y] = true
}
}
}
while !queue.isEmpty {
let coordinate = queue.dequeue()!
for (dx, dy) in zip(dxs, dys) {
let x = coordinate.x + dx
let y = coordinate.y + dy
if x < 0 || x >= graph.count || y < 0 || y >= graph[0].count || graph[x][y] == Int.min { continue }
if isVisited[x][y] == false {
queue.enqueue((x, y))
answer[x][y] = answer[coordinate.x][coordinate.y] - 1
isVisited[x][y] = true
}
}
}
return answer
}
func bfs(graph: [[Int]], fireGraph: [[Int]], startCoordinate: (x: Int, y: Int)) -> Int {
let dxs = [0, 0, -1, 1]
let dys = [-1, 1, 0, 0]
var queue = Queue<(x: Int, y: Int)>()
var answer: [[Int]] = Array(repeating: Array(repeating: 0, count: graph[0].count), count: graph.count)
var isVisited: [[Bool]] = Array(repeating: Array(repeating: false, count: graph[0].count), count: graph.count)
queue.enqueue(startCoordinate)
isVisited[startCoordinate.x][startCoordinate.y] = true
answer[startCoordinate.x][startCoordinate.y] = 1
while !queue.isEmpty {
let coordinate = queue.dequeue()!
if coordinate.x == 0 || coordinate.x == (graph.count - 1) || coordinate.y == 0 || coordinate.y == (graph[0].count - 1) {
return answer[coordinate.x][coordinate.y]
}
for (dx, dy) in zip(dxs, dys) {
let x = coordinate.x + dx
let y = coordinate.y + dy
if x < 0 || x >= graph.count || y < 0 || y >= graph[0].count || graph[x][y] == Int.min { continue }
if isVisited[x][y] == false {
isVisited[x][y] = true
if answer[coordinate.x][coordinate.y] + 1 < abs(fireGraph[x][y]) || fireGraph[x][y] == 0 {
queue.enqueue((x, y))
answer[x][y] = answer[coordinate.x][coordinate.y] + 1
}
}
}
}
return 0
}
func solution4179() {
let miroInfos = readLine()!.split(separator: " ").map { Int($0)! }
let (R, C) = (miroInfos[0], miroInfos[1])
var graph: [[Int]] = []
var jihoonCoordinate = (x: 0, y: 0)
for x in 0..<R {
let arr: [Int] = Array(readLine()!).map { val in
switch val {
case "J":
return 1
case "F":
return -1
case "#":
return Int.min
default:
return 0
}
}
if arr.contains(1) {
let y = arr.firstIndex(of: 1)!
jihoonCoordinate = (x, y)
}
graph.append(arr)
}
let fireGraph = bfsFire(graph: graph)
let answer = bfs(graph: graph, fireGraph: fireGraph, startCoordinate: jihoonCoordinate)
if answer == 0 {
print("IMPOSSIBLE")
} else {
print(answer)
}
}
solution4179()- 반례와 문제점은 이 분 블로그를 참고하여 다시 코드를 작성하였다.
- 기존에는 BFS내에서 한번 더 BFS를 돌리는? 불필요한 작업이 발생하였는데, 새롭게 작성할 때는 불이 다 퍼진 상황을 먼저 BFS를 사용하여 그래프를 확보하고 이를 바탕으로 지훈이가 탈출 할 수 있는지 BFS를 사용하였다.
if answer[coordinate.x][coordinate.y] + 1 < abs(fireGraph[x][y]) || fireGraph[x][y] == 0 {
queue.enqueue((x, y))
answer[x][y] = answer[coordinate.x][coordinate.y] + 1
}- 일반적인 BFS랑 크게 다를 건 없지만 이 부분이 이번 문제의 핵심로직이었던것 같다.
- 기존 불이 존재한다면 불의 시간 초와 비교하여 이동을 시킬지 말지에 대한 여부, 그 외에 불이 접근하지 못해 안전한 공간이면 곧바로 이동할 수 있게 만드는 로직이었다.
반응형