[Swift] 백준 토마토 7569

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

 

 

1. 문제이해

• M: 상자의 가로, N: 상자의 세로, H: 상자 갯수
• 3차원 배열 형태의 토마토 상자
• 익은 토마토 주변에 있는 토마토는 하루가 지나면 익은 토마토가 된다.
• 주변의 범위는 토마토의 앞, 뒤, 좌, 우 그리고 위에 있는 상자와 아래에 있는 상자에 대한 토마토 총 6방향
• 모든 토마토가 익기 위해서 며칠 걸리는지 구하기

 

2. 접근방법

• 일반적인 BFS에서 윗 상자와 아랫 상자에 있는 토마토의 경우가 추가 됨
• 예시)

0 0 0 0 0        0 0 0 0 0

0 0 0 0 0        0 0 1 0 0

0 0 0 0 0  →   0 0 1 0 0

0 0 1 0 0         0 1 1 1 0

 

토마토는 3차원 배열이지만 2차원 배열 만들어서 코드 작성해보기

3. 코드

import Foundation

func solution(){
    var input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let M = input[0] // 가로
    let N = input[1] // 세로
    let H = input[2] // 상자 갯수
    var map = [[Int]]()
    let dx = [1,0,0,-1]
    let dy = [0,1,-1,0]
    var count = 0 // 모든 토마토가 익기까지 걸리는 날짜
    var queue = [(Int, Int)]()
    
    for _ in 0..<N*H{
        map.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }
    
    for i in 0..<map.count{
        for j in 0..<map[i].count{
            if map[i][j] == 1{
                queue.append((i,j))
            }
        }
    }
    
    // BFS
    while !queue.isEmpty{
        var newQueue = [(Int, Int)]()
        for q in queue{
            for index in 0..<dx.count{
                let nx = q.0 + dx[index]
                let ny = q.1 + dy[index]
                var a = q.0 / N + 1
                
                if nx >= N * a - N && nx < N * a && ny >= 0 && ny < M && map[nx][ny] == 0{
                    map[nx][ny] = 1
                    newQueue.append((nx,ny))
                }
            }
            // 윗 상자와 아랫 상자에 대한 경우
            let up = q.0 - N
            let down = q.0 + N
            if up >= 0 && map[up][q.1] == 0{
                map[up][q.1] = 1
                newQueue.append((up, q.1))
            }
            if down < N*H && map[down][q.1] == 0{
                map[down][q.1] = 1
                newQueue.append((down, q.1))
            }
        }
    
        if newQueue.isEmpty{
            break
        }
        queue = newQueue
        count += 1
    }
    
    var complete = true
    for i in 0..<map.count{
        for j in 0..<map[i].count{
            if map[i][j] == 0{
                complete = false
            }
        }
    }
    
    print(complete ? count : -1)
    
}
solution()