[Swift] 백준_토마토(7576)

문제

 

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

7576번: 토마토

 

 

풀이

 

BFS문제이며, 이전과는 달리 시작점이 하나가 아니라 여러 개인 문제였다.

 

크게 다를 것 없이 처음에 반복문으로 큐에 시작점들을 미리 넣어놓기만 하면 똑같다.

 

하루마다 주변 토마토를 익게 하기 때문에 주변 토마토까지의 최소 거리를 계산해주면된다. 이때, 0인 곳에만 토마토가 있으므로 -1이거나 0보다 큰 토마토에 대해서는 계산하지 않아도 된다.

 

여기서 처음에는 더 멀리 있는 토마토의 주변 연산이 먼저 실행될 수도 있어서 0이 아니라 0보다 큰 값에 대해서도 더 작은 값이 나오면 바꿔주어야 하는거아닌가 하는 생각이 들었었다.

근데 생각해보니 큐는 먼저들어온게 먼저 나간다. 그래서 한쪽 연산이 모두 수행될 가능성이 없고 1일차, 2일차, 3일차 이렇게 차례대로 연산이 진행될 수 있다. 바보같은 생각이었음.

import Foundation
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var left: [[Int]] = []
var right: [[Int]] = []
var tomato: [[Int]] = []
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var minDay = 1
for _ in 0..<input[1] {
    tomato.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
//큐에 미리 넣어놓기
for i in 0..<input[1] {
    for j in 0..<input[0] {
        if tomato[i][j] == 1 {
            left.append([i,j])
        }
    }
}
//BFS
while !left.isEmpty || !right.isEmpty {
    if right.isEmpty {
        right = left.reversed()
        left.removeAll()
    }
    let current = right.removeLast()
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        if newX < 0 || newY < 0 || newX >= input[1] || newY >= input[0] {
            continue
        }
        if tomato[newX][newY] == 0 {
            tomato[newX][newY] = tomato[current[0]][current[1]] + 1
            minDay = max(minDay, tomato[newX][newY])
            left.append([newX,newY])
        }
    }
}
minDay -= 1
outer: for i in 0..<input[1] {
    for j in 0..<input[0] {
        if tomato[i][j] == 0 {
            minDay = -1
            break outer
        }
    }
}
print(minDay)

 

다른 사람들의 답변을 보니 큐를 이용할때 인덱스를 이용하는 분들이 많았다.

 

생각해보니 큐에는 계속해서 append가 되고, pop된 것들은 사용되지 않으므로 인덱스를 이용해도 괜찮아보였고 심지어 시간도 reversed()보다 덜 걸릴 것 같았다.

 

인덱스 변수를 두고 반복문마다 1씩 증가시켜주면 queue[idx]값을 이용해 연산을 진행할 수 있다. 이 과정은 idx가 queue의 count보다 같아질때까지 반복하면 된다.

import Foundation
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var queue: [[Int]] = []
var tomato: [[Int]] = []
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var minDay = 1
for _ in 0..<input[1] {
    tomato.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
//큐에 미리 넣어놓기
for i in 0..<input[1] {
    for j in 0..<input[0] {
        if tomato[i][j] == 1 {
//            left.append([i,j])
            queue.append([i,j])
        }
    }
}
//BFS
var idx = 0
while idx < queue.count {
    let current = queue[idx]
    idx += 1
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        if newX < 0 || newY < 0 || newX >= input[1] || newY >= input[0] {
            continue
        }
        if tomato[newX][newY] == 0 {
            tomato[newX][newY] = tomato[current[0]][current[1]] + 1
            minDay = max(minDay, tomato[newX][newY])
            queue.append([newX,newY])
        }
    }
}
minDay -= 1
outer: for i in 0..<input[1] {
    for j in 0..<input[0] {
        if tomato[i][j] == 0 {
            minDay = -1
            break outer
        }
    }
}
print(minDay)

확실히 시간이 조금 줄어들었다.

 

____________________________________________________________________________________________________

 

큐를 사용할때 인덱스를 이용할 수도 있다는 것을 알고있어야할듯

 

시작점이 여러개일땐 큐에 미리 넣어놓고 시작하면 된다.