글 읽기 - swift 시간초과 나는데 어디를 수정해야 할까요 ..

spqjf12345 2년 전 0

swift 코드 제출시 시간초과가 나는데 어디가 문제일까요 ..?

제 생각엔 removeFirst()가 O(n)인게 문제가 되는거 같은데 O(1)로 바꿀 방법이 있을까요 ?

알려주시면 감사하겠습니다.

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/08.
//

import Foundation
var line = readLine()!.split(separator: " ").map { Int(String($0))! }
var n = line[0]
var m = line[1]

var dx = [-1, 1, 0, 0]
var dy = [0, 0, 1, -1]

var map = [[Int]]()
var visit: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: m), count: n) // x, y, 벽 부순 적 있는지

func bfs() -> Int {
    var queue = [(Int, Int, Int)]() // x, y, 벽 부쉈는지
    queue.append((0, 0, 0))
    visit[0][0][0] = 1 // 0, 0, 0(벽 안부숴도 됨)
    
    while(!queue.isEmpty) {
        let x = queue.first!.0
        let y = queue.first!.1
        let isBreak = queue.first!.2
        
        queue.removeFirst()
        if(x == n-1 && y == m-1) { return visit[x][y][isBreak] }
        for i in 0..<4 {
            let nx = dx[i] + x
            let ny = dy[i] + y
            if(nx >= n || ny >= m || nx < 0 || ny < 0 ) { continue }
            
            if(visit[nx][ny][isBreak] != 0) { continue }

            if(map[nx][ny] == 0) {
                visit[nx][ny][isBreak] = visit[x][y][isBreak] + 1
                queue.append((nx, ny, isBreak))
            }else if(map[nx][ny] == 1 && isBreak == 0){ // 기회 안사용 했을때
                visit[nx][ny][1] = visit[x][y][isBreak] + 1
                queue.append((nx, ny, 1)) // 부술 기회 사용
            }
            
            
        }
        
    }
    return -1
}

for _ in 0..<n {
    let l = readLine()!.map { Int(String($0))! }
    map.append(l)
}

print(bfs())

wapas 2년 전 1

Queue를 직접 구현하시면 됩니다.

추상적 자료형 특성상 Queue를 구현하는 방법은 여러가지가 있습니다.

Swift에서는 array.reversed()가 O(1)임을 이용하여 구현한 큐가 있고, 아니면 연결리스트로 구현한 큐도 있습니다.

spqjf12345 2년 전 1

감사합니다 ㅠ

reversed()가 O(1)인지 몰랐네요 .. 정말 감사합니다

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

문제

문제

출처

ICPC

swift 시간초과 나는데 어디를 수정해야 할까요 ..

spqjf12345 2년 전 0

wapas 2년 전 1

spqjf12345 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말