[Swift 알고리즘] 백준 2206 - 벽 부수고 이동하기

안녕하세요 코코종입니다~

이번에는 좀 어려웠던..ㅜㅜㅜ 문제를 들고왔어요.

순서로는 나이트 이동하기 보다 먼저 풀어서 나중에 나이트 문제를 풀 때 좀 수월했답니다!

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

2206번: 벽 부수고 이동하기

//
//  main.swift
//  Algorithm
//
//  Created by kokojong on 2022/03/28.
//

//6 4
//0100
//1110
//1000
//0000
//0111
//0000

// 15

//import Foundation

// 2206 벽 부수고 이동하기

//let data = readLine()!.components(separatedBy: " ").map( {Int($0)!})
let data = readLine()!.split(separator: " ").map( {Int(String($0))!})
let n = data[0]
let m = data[1]

// 0 -> 이동가능, 1 -> 막힘
var board: [[Int]] = []

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

var result = -1 // 안되면 -1

// 0~n-1 행, 0~m-1열, 내부에는 [방문정보, 부순 여부]
var visited = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: m), count: n)

var queue: [[Int]] = [] // n,m (행, 열)

//queue.append([0,0])


// 우 하 좌 상
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]

queue = [[0,0,0]]
visited[0][0][0] = 1
var index = 0
// 강제로 하나를 뚫고 해본다면? (모든 경우)
        
while queue.count > index {
    
//    let q = queue.removeFirst()
    let q = queue[index]
    index += 1
    let r = q[0]
    let c = q[1]
    let crash = q[2]
    
    if r == n-1 && c == m-1 {
        result = visited[r][c][crash]
        break
    }
    
    for i in 0..<4 {
        let cc = c + dx[i] // x좌표(열)
        let rr = r + dy[i] // y좌표(행)
        
        if  cc < m && cc >= 0 && rr < n && rr >= 0  && visited[rr][cc][crash] == 0 { // board의 범위안에 있고, 방문 가능하다면
            if board[rr][cc] == 0 { // 안 부수고 방문 가능
                visited[rr][cc][crash] = visited[r][c][crash] + 1
                queue.append([rr,cc,crash])
                
            } else if crash == 0 { // 부술 수 있다면
                visited[rr][cc][1] = visited[r][c][crash] + 1
                queue.append([rr,cc,1])
                
            }
        }
    }
    
}

print(result)
//print(visited)

 

---

 

후... 너무 어려워서 애를 먹었던 문제입니다. 처음에는 기본 BFS에 벽중에 하나를 부순 경우(O(n^2)이 곱해진...)를 구해봤는데 역시나 시간초과가 나더라구요.. 그래서 어떻게 해야하나 아무리 고민해도 모르겠어서 슬쩍 답을 참고했습니다.

visited를 2차원 배열이 아닌 3차원 배열로 만들고 부숴진 여부와 방문여부를 저장했습니다.

 

이후에 방문해가면서 안부수고 이동이 가능한 경우, 부숴야 하는데 부술수 있는 경우(아직 아무것도 안부순 경우)로 나눠서 BFS를 진행했습니다.

 

그래도 시간초과가 났었는데요...(하... 스위프트 진짜...) components대신 split으로 바꾸면서 import를 제거했고, queue.removeFirst() 가 O(N)이라 너무 오래 걸려서 queue는 그대로 두고 해당 인덱스에 접근하는 식으로 했습니다. (이와 동시에 while문의 조건도 바꿨습니다)

 

이번에는 알고리즘도 어려웠고, 시간초과로 고생했던 문제였습니다 ㅜㅜ (+백준이 서버가 이상했는지 막 15분 지나야 채점되고 이랬네요... 백준 싫어) 스터디원이 시간초과에 대한 도움을 주셔서 다행히 완료했답니당!