글 읽기 - Swift 시간초과

gearmamn06 5년 전 0

input 부분에서 que를 설정하고 전체 썩지 않은 토마토의 갯수를 새어서

최초 전체 토마토중 썩은 토마토를 찾는 이중루프(==1) 과

마지막단계에서 전체 토마토가 썩었는지 판단하는 경우를 검색하기 위한 이중루프를 피할려고 했습니다.

위에서 말한 조치를 하던 안하던 체점 초반부에서 시간초과가 뜨는데 어느부분이 문제인지 모르겠습니다.

알고리즘 전체를 바꾸거나 시간을 더 줄일 수 있는 방법이 있을까요?

import Foundation


let MN = readLine()!.components(separatedBy: " ").map{ Int($0)! }

let M = MN.first!; let N = MN.last!

var mat = [[Int]]()
var count = 0

var lev = 0
var q = [(Int, Int)]()

mat.append([Int](repeating: -1, count: M + 2))
for i in 0..<N {
    var m = readLine()!.components(separatedBy: " ").map{ Int($0)! }

    for j in 0..<m.count {
        if m[j] == 1 {
            q.append((i + 1, j + 1))
        }else if m[j] == 0 {
            count += 1
        }
    }
    m.insert(-1, at: 0); m.append(-1)
    mat.append(m)
}
mat.append([Int](repeating: -1, count: M + 2))

let directions = [(0, -1), (-1, 0), (1, 0), (0, 1)]

var c = 0
while !q.isEmpty {
    lev += 1
    
    for _ in 0..<q.count {
        let f = q.removeFirst()
        for d in directions {
            let nn = d.0 + f.0; let nm = d.1 + f.1
            if mat[nn][nm] == 0 {
                c += 1
                mat[nn][nm] = lev
                q.append((nn, nm))
            }
        }
    }
}

var days = max(lev - 1, -1)
days = count == c ? days : -1

print(days)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Swift 시간초과

gearmamn06 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말