글 읽기 - 어디서 시간초과가 나는 걸까요 ? (Swift) + 파이썬 결과..

tksrl0379 3년 전 0

어떤 부분 때문에 시간초과가 있는건지 모르겠네요 ... ㅠㅠ

도대체 어디를 잘 못 했을까요..

파이썬으로 돌려보니 통과하네요..

import Foundation

let input = readLine()!.components(separatedBy: " ").map{ Int($0)! }
let N = input[0]
let M = input[1]
var matrix = [[Character]]()
(0..<N).forEach { _ in matrix.append(Array(readLine()!)) }
var visited = Array(repeating: Array(repeating: [0, 0], count: M), count: N)


func bfs(matrix: [[Character]]) -> Int {
    
    
    let dx = [-1, 0, 1, 0]
    let dy = [0, 1, 0, -1]
    
    var queue = [(0, 0, 1)] // y, x, cnt, 벽 부시기
    visited[0][0][1] = 1
    
    while !queue.isEmpty {
        var y: Int!, x: Int!
        var crash: Int!
        
        (y, x, crash) = queue.removeFirst()
        
        if y == N-1 && x == M-1 {
            return visited[y][x][crash]
        }
        
        for i in 0..<4 {
            let ny = y + dy[i]
            let nx = x + dx[i]
            
            if (0..<N) ~= ny && (0..<M) ~= nx {
                if matrix[ny][nx] == "0" && visited[ny][nx][crash] == 0 {
                    visited[ny][nx][crash] = visited[y][x][crash] + 1
                    queue.append((ny, nx, crash))
                } else if matrix[ny][nx] == "1" && crash == 1 {
                    visited[ny][nx][0] = visited[y][x][1] + 1
                    queue.append((ny, nx, 0))
                }
            }
        }
    }
    return -1
}

print(bfs(matrix: matrix))

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

문제

문제

출처

ICPC

어디서 시간초과가 나는 걸까요 ? (Swift) + 파이썬 결과..

tksrl0379 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말