[Swift 알고리즘] 백준 BOJ - 7576 토마토

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 7576 토마토" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

7576번: 토마토

 

---

풀이

이번 문제는 bfs 문제입니다.

상하좌우로 토마토 익힘이 번질 때 최소 일수를 구해야 하므로 dfs로 해결은 불가능합니다.

 

저는 queue에 x, y, day를 저장하여 day를 1씩 증가시키며 queue에 push를 해주었습니다.

 

queue의 원소를 참조할 때 중요한 점은 맨 앞의 원소를 pop 시키면 안 된다는 의미입니다.

정확히는 맨 앞 원소를 "삭제"하면 안 됩니다.

왜냐하면 Array에서 맨 앞 원소를 지우게 되면 뒷 원소를 앞으로 옮기는 작업이 추가가 되어 시간 초과가 발생합니다.

따라서 index를 1씩 증가시키며 참조하는 방법으로 queue의 원소에 접근해야 합니다.

 

마지막에 전체 상자 개수 - 빈 칸의 개수와 토마토의 개수를 세서 같다면 day를, 다르다면 -1을 출력하면 됩니다.

 

---

전체 코드

//7576 토마토
import Foundation

let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
let w = input[0], h = input[1]
var result = 0
var blankCount = 0, tomatoCount = 0

var boxes: [[Int]] = []
for _ in 0..<h {
    let tomatoes = readLine()!.split { $0 == " " }.map { Int(String($0))! }
    boxes.append(tomatoes)
    blankCount += (tomatoes.filter { $0 == -1 }.count)
}

var queue: [(x: Int, y: Int, day: Int)] = []
let di: [Int] = [1, -1, 0, 0]
let dj: [Int] = [0, 0, -1, 1]

for i in 0..<h {
    for j in 0..<w {
        if boxes[i][j] == 1 {
            queue.append((i, j, 0))
            tomatoCount += 1
        }
    }
}

var index = 0
while index < queue.count {
    let tomato = queue[index]
    index += 1
    
    for i in 0..<4 {
        let nx = tomato.x + di[i]
        let ny = tomato.y + dj[i]
        let nextDay = tomato.day + 1

        if nx >= 0 && nx < h && ny >= 0 && ny < w && boxes[nx][ny] == 0 {
            queue.append((nx, ny, nextDay))
            boxes[nx][ny] = 1
    
            tomatoCount += 1
            result = nextDay
        }
    }
}

if tomatoCount == w * h - blankCount {
    print("\(result)")
} else {
    print(-1)
}

 

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.