글 읽기 - [Swift] 문제해결에 도움을받고싶습니다

whdvy3 2년 전 0

계속해서 시간초과가 나는데 혹시 이유를 알 수 있을까요?

let nmk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nmk[0]
let m = nmk[1]
let k = nmk[2]
var arr = [[Int]]()
let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 11), count: m + 1), count: n + 1)
var queue = [((Int, Int),Int,Int)]() //좌표, 이동한 벽개수, 부술 수 있는 벽의 개수
var idx = 0
var result = -1
for _ in 0..<n{
    arr.append(readLine()!.map{Int(String($0))!})
}

func bfs(){
    queue.append(((0,0),1,k))
    visited[0][0][k] = true
    while queue.count > idx{
        let pop = queue[idx]
        if pop.0.0 == n - 1 && pop.0.1 == m - 1{
            result = pop.1
            break
        }
        for i in 0..<4{
            let nx = pop.0.0 + dx[i]
            let ny = pop.0.1 + dy[i]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m {
                if pop.2 > 0 && arr[nx][ny] == 1 && !visited[nx][ny][pop.2 - 1] {
                    queue.append(((nx,ny),pop.1 + 1,pop.2 - 1))
                    visited[nx][ny][pop.2 - 1] = true
                }
                
                if arr[nx][ny] == 0 && !visited[nx][ny][pop.2]{
                    queue.append(((nx,ny),pop.1 + 1,pop.2))
                    visited[nx][ny][pop.2] = true
                }
            }
        }
        idx += 1
    }
}
bfs()
print(result)

wapas 2년 전 1

Swift가 느려서 시간 초과가 발생하는 것 같네요.

같은 로직으로 다른 빠른 언어(ex. c++)로 제출한다면 발생하지 않았을 것으로 보입니다.

제가 직접 제출해보니 프로그램이 좀 더 빠르게 수행할 수 있게 최적화를 잘해서 제출하면 약 1900ms 시간으로 "맞았습니다!"가 나옵니다.

그러나 아이디어 하나만 적용하면 1900ms에서 1300ms로 수행 시간을 단축 할 수 있습니다.

n이 음이 아닌 정수 일 때

x, y 좌표에 k번 벽을 파괴해서 도달했을 때 (x, y, k) 라고 합시다.

이미 이전에 (x, y, k - n)을 방문했다면 (x, y, k)를 볼 필요가 있을까요?

이 점을 이용하면 whdvy3님 Swift 코드로도 "맞았습니다!"가 나올 수 있습니다.

whdvy3 2년 전 0

벽을 더 많이 부수고 갔을 경우가 적게 부수고 갔을때 보다 값이 작다..라는 의미인가요?

이해를 잘 못하겠습니다..ㅠㅠ

wapas 2년 전 2

x, y 좌표에서 목표 지점 n, m으로 가는데 벽을 3번 부셔야 한다고 가정합시다.

0, 0 좌표에서 x, y 좌표까지 벽을 1번 부수고 도착한 적이 있다고 합시다.

그러면 0, 0 좌표에서 x, y 좌표까지 벽을 1번 부수고, x, y 좌표에서 n, m 좌표로 가는데 벽을 3번 부스고 도착하니, 0, 0에서 n, m으로 가는데 벽을 총 4번 부셔야 합니다. <--- 이 과정을 A라고 합시다.

BFS 도중에 똑같은 x, y 좌표에서 벽을 5번 부수고 도달했다고 합시다.

그러면 0, 0 좌표에서 x, y 좌표까지 벽을 5번 부수고, x, y 좌표에서 n, m 좌표로 가는데 벽을 3번 부스고 도착하니, 0, 0에서 n, m으로 가는데 벽을 총 8번 부셔야 합니다. <--- 이 과정을 B라고 합시다.

이렇게 본다면 B과정에서 'x, y -> n, m' 탐색은 전혀 보지 않아도 됩니다.

문제에서 구하는 것은 최단 거리고, 이미 이전에 A 과정이라는 최단 거리를 구했기 때문입니다.

정리하면 어떤 좌표에 방문했는데, 이미 이전에 벽을 적게 파괴해서 도달한 적이 있다면 "지금 현재 상태가 벽을 더 많이 파괴했으므로(= 벽을 파괴하여 더 많이 이동했으므로)" 지금 상태에서는 최단 거리가 될 수 없습니다.

wapas 2년 전 2

좀 더 자세히 설명하자면

0111111111
1111111111
1111111111
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

경우에서 좌측 최상단 3x3 영역만 살펴 보겠습니다.
현재 위치를 X라고 표시하겠습니다. ( 이때 K는 10이라고 하겠습니다 )

K = 10 (A 상황)
X11
111
111

(벽을 파괴한 후 아래쪽으로 이동)
K = 9
011
X11
111

(벽을 파괴한 후 왼쪽으로 이동)
K = 8
011
1X1
111

(벽을 파괴한 후 위쪽으로 이동)
K = 7
0X1
111
111

(왼쪽으로 이동)
K = 7 (B 상황)
X11
111
111

(벽을 파괴한 후 아래쪽으로 이동)
K = 6
011
X11
111

(벽을 파괴한 후 왼쪽으로 이동)
K = 5
011
1X1
111

(벽을 파괴한 후 위쪽으로 이동)
K = 4
0X1
111
111

(왼쪽으로 이동)
K = 4 (C 상황)
X11
111
111

... (생략)

visited를 [x][y][k]로 했기 때문에 A, B, C 상황 모두 다른 상황으로 인식하고 있습니다.
저희는 최단 거리만 보면 되는 상황이기에 A 상황을 마주친적이 있다면 B, C 상황을 만났을 때 B, C를 탐색하지 않아도 됩니다.

whdvy3 2년 전 1

무슨말씀이신지 이해를 하겠는데 제 수준에서는 코드로 도저히 구현이 불가능하네요..

나중에 다시시도해봐야겠습니다..

whdvy3 2년 전 0

인접한 네방향을 탐색하면서 이전에 벽이 하나 더 있을때 탐색한곳을 탐색하려하면 continue로 무시해줘서 위에서 말씀하신 상황인 B와 C상황을 안들어가게 해주었지만 시간초과가 났습니다.

잘못처리해준걸까요?

let nmk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nmk[0]
let m = nmk[1]
let k = nmk[2]

var impossible = true
var arr = [[Int]]()
for _ in 0..<n{
    arr.append(readLine()!.map{Int(String($0))!})
}

func bfs(){
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    var queue = [((Int, Int), Int, Int)]()//x좌표, y좌표, 이동횟수, 부순벽의개수
    var visited = Array(repeating: Array(repeating: Array(repeating: false, count: k + 2), count: m), count: n)
    queue.append(((0, 0), 1, k))
    visited[0][0][k] = true
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        let x = pop.0.0
        let y = pop.0.1
        let moveCnt = pop.1
        let wall = pop.2
        
        if x == n - 1 && y == m - 1{
            print(moveCnt)
            impossible = false
            break
        }
        
        for i in 0..<4{
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n || ny < 0 || ny >= m {continue}
            if visited[nx][ny][wall + 1]{continue}
            if arr[nx][ny] == 1 && wall > 0 && !visited[nx][ny][wall - 1]{
                queue.append(((nx, ny), moveCnt + 1, wall - 1))
                visited[nx][ny][wall - 1] = true
            }
            if arr[nx][ny] == 0 && !visited[nx][ny][wall]{
                queue.append(((nx, ny), moveCnt + 1, wall))
                visited[nx][ny][wall] = true
            }
            
        }
        
    }
    
}
bfs()
if impossible{
    print(-1)
}

wapas 2년 전 1

if visited[nx][ny][wall + 1]{continue} 에서, 처리를 못하는 케이스가 있는 것 같습니다.

예를 들어서

x, y에 처음 방문 했을 당시 벽을 부순 횟수가 4라서 visited[x][y][4]를 true로 저장했다고 합시다.

x,y 두 번째로 방문했을 때는 벽을 부순 횟수가 1이라서 visited[x][y][1 + 1]은 false이므로 visited[x][y][4]를 true 해준 의미가 없어지게 됩니다.

whdvy3 2년 전 0

아직까지 도저히 모르겠는데,, 혹시 어느부분을 어떻게 고쳐야할지 알려주실수 있나요?

wapas 2년 전 1

풀이법은 다양하게 있을 것 같은데 제가 사용한 풀이법은 아래와 같습니다.

visited 배열을 3차원으로 두지 않고 2차원으로 둡니다. 대신 Bool 자료형을 담는게 아닌 Int 자료형을 담습니다.

그리고 visited 배열을 아래와 같이 정의를 했습니다. visited[y][x] 값을 k라고 할 때,

y, x 좌표에 방문했을 때, k가 -1이면 그 좌표는 한 번도 방문하지 않았음을 의미하는 것이고

k가 0이상 이면 그 좌표에 방문 했을 때, 벽을 k번 파괴하고 도달했다는 의미입니다.

예를들어 현재 y, x 좌표에서 벽을 5번 부셔서 도착 했는데, visited[y][x]가 1이면 그 정점은 더 이상 탐색할 필요가 없어집니다.

whdvy3 2년 전 1

드디어 해결했습니다 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

[Swift] 문제해결에 도움을받고싶습니다

whdvy3 2년 전 0

wapas 2년 전 1

whdvy3 2년 전 0

wapas 2년 전 2

wapas 2년 전 2

whdvy3 2년 전 1

whdvy3 2년 전 0

wapas 2년 전 1

whdvy3 2년 전 0

wapas 2년 전 1

whdvy3 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말